gistfile1.cpp

#include <bits/stdc++.h>

#ifdef _MSC_VER
#include <hash_set>
#include <hash_map>
using namespace stdext;
#else
#include <ext/hash_set>
#include <ext/hash_map>
using namespace __gnu_cxx;
#endif

#define all(v)          v.begin(),v.end()
#define allr(v)         v.rbegin(),v.rend()
#define rep(i,m)        for(int i=0;i<(int)m;i++)
#define REP(i,k,m)      for(int i=k;i<(int)m;i++)
#define mem(a,b)        memset(a,b,sizeof(a))
#define mp              make_pair
#define pb              push_back
#define X real()
#define Y imag()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef complex<long double> point;

#define effort first
#define points second

int diri[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
int dirj[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int compare(double d1, double d2) {
	if (fabs(d1 - d2) < 1e-9)
		return 0;
	if (d1 < d2)
		return -1;
	return 1;
}

#define OO ((int)1e9)
#define MAX 1000001
#define MOD 1000000009
int n, k;
vector<pair<int, int> > players;
int sv[102][102][102];

int dp(int ind, int rem, int rank, int &curp) {
	if (ind == n) {
		if (!rem && rank <= k)
			return 0;
		return OO;
	}
	int &x = sv[ind][rem][rank];
	if (x != -1)
		return x;
	// he wins
	x = dp(ind + 1, rem, rank - (players[ind].points + 1 < curp), curp);
	//i win
	x = min(x,
			dp(ind + 1, rem - 1, rank - (players[ind].points <= curp),
					curp) + players[ind].effort);
	return x;
}
int main() {
	std::ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	cin >> n >> k;
	players = vector<pair<int, int> >(n);
	rep(i,n)
		cin >> players[i].points >> players[i].effort;
	sort(all(players));
	int best = OO;
	for (int i = 0; i <= n; ++i) {
		mem(sv, -1);
		best = min(best, dp(0, i, n + 1, i));
	}
	cout << ((best >= OO)? -1 : best) << endl ;
	return 0;
}