#include <fstream>
#include <algorithm>

#define Inf 1234567
#define MaxG 1005
#define MaxW 5010

using namespace std;

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

int dp[MaxW], G, W, eg, cg;

int main() {
	fill(dp, dp + MaxW, Inf);
	dp[0] = 0;

	fin >> G >> W;

	for (int i = 1; i <= G; ++i) {
		fin >> eg >> cg;
		for (int j = W; j >= 0; --j) {
			if (dp[j] != Inf && j + eg < MaxW && dp[j + eg] > dp[j] + cg) {
				dp[j + eg] = dp[j] + cg;
			}
		}
	}

	fout << dp[W] << '\n';

	return 0;
}