#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int G(0),
	W(0);

int v[1001],
	c[1001];

int a[10001];

bool folosit[10001][1001];

int tot(0);

int main(int argc, char *argv[]) {
	ifstream fin("energii.in");
	fin >> G >> W;
	for (int i(0); i < G; ++i) {
		fin >> v[i] >> c[i];
		tot += v[i];
	}
	fin.close();

	tot %= 10001;

	memset(a, -1, sizeof(a));
	memset(folosit, 0, sizeof(folosit));

	a[0] = 0;
	for (int i(1); i <= tot; ++i)
		for (int j(0); j < G; ++j) {
//				cout << i << " " << j << " " << v[j] << " " << i - v[j] << " " << a[i - v[j]] << " " << folosit[i - v[j]][j] << endl;
			if ((v[j] <= i) && (!folosit[i - v[j]][j]) && (a[i - v[j]] != -1)) {
//				cout << j << endl;
				if ((a[i] > a[i - v[j]] + c[j]) || (a[i] == -1)) {
					a[i] = a[i - v[j]] + c[j];
					for (int k(0); k < G; ++k)
						folosit[i][k] = folosit[i - v[j]][k];
					folosit[i][j] = true;
				}
			}
		}

//	for (int i(0); i <= W; ++i)
//		cout << a[i] << " ";
//	cout << endl;

	int r(-1);
	for (int i = W; i <= tot; ++i)
		if (a[i] != -1)
			if ((r == -1) || (a[i] < r))
				r = a[i];

	ofstream fout("energii.out");
	fout << r << endl;
	fout.close();

	return 0;
}