// Craciun Catalin
//  Energii
//   Infoarena
#include <iostream>
#include <cstring>
#include <fstream>

struct obj {
	
	int val, weight;
};

using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");

#define GMax 10005

int V[GMax];
bool T[GMax];
int n,weight;

int main() {
	
	f>>n>>weight;
	memset(V, 0, sizeof(V));
	memset(T, false, sizeof(T));
	
	for (int i=1;i<=n;i++) {
		int oVal, oWeight;
		f>>oWeight>>oVal;
		for (int j=weight; j>=oWeight;j--) {
			if (!T[j-oWeight]) {
				V[j] = oVal;
				T[j] = true;
			} else if (V[j-oWeight] + oVal < V[j])
				V[j] = V[j-oWeight] + oVal;
		}
	}
	
	g<<V[weight]<<'\n';
	
	f.close();
	g.close();
	
	return 0;
}