#include <iostream>
#include <fstream>
#include <algorithm>


const int NMAX = 1005;


struct Obiect {

	int v;
	int w;

};


Obiect Obiecte[NMAX];
int prev[5002];

int Knapsack(int N, int GMax) {

	for (int i = 1; i <= N; ++i) {

		int curr[5002] = {};
		for (int j = 1; j <= GMax; ++j) {

			if (Obiecte[i].w > j) {
				curr[j] = prev[j];
			}
			else {
				curr[j] = std::max(prev[j], prev[j - Obiecte[i].w] + Obiecte[i].v);
			}

		}

		for (int j = 1; j <= GMax; ++j) {
			prev[j] = curr[j];
		}

	}

	return prev[GMax];

}


int main() {

	std::ifstream in("energii.in");
	std::ofstream out("energii.out");

	int N, G;
	in >> N >> G;

	int SumaTotalaW = 0;
	int SumaTotalaV = 0;
	for (int i = 1; i <= N; ++i) {
		in >> Obiecte[i].w >> Obiecte[i].v;
		SumaTotalaW += Obiecte[i].w;
		SumaTotalaV += Obiecte[i].v;
	}

	out << SumaTotalaV - Knapsack(N, SumaTotalaW - G);
	

	system("PAUSE");
	return 0;
}