#include<fstream>
using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int dp[5001], g, w, energie[1001], cost[1001];

int main() {
	int i, j, aux, poz;
	fin >> g >> w;
	for(i = 1; i <= g; i++) {
		fin >> energie[i] >> cost[i];
	}

	for(j = 1; j <= w; j++) dp[j] = -1;
	for(i = 1; i <= g; i++) {
		for(j = w; j >= 1; j--) {
			poz = (j - energie[i] <= 0) ? 0 : j - energie[i];
			aux = -1;
			if(dp[poz] != -1) {
				aux = dp[poz] + cost[i];
			}
			if(dp[j] != -1 && dp[j] < aux) {
				aux = dp[j];
			}
			dp[j] = aux;
		}
		/*for(j = 1; j <= w; j++) {
			fout << dp[j] << " ";
		}
		fout << endl;*/
	}
	fout << dp[w];
	return 0;
}