#include <iostream>
#include <fstream>




#define NUMAR_GENERATOARE 1001
#define NECERSAR_PORNIRE 5001
#define INFINITY 9999999



using namespace::std;




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




int nr_gen, cantitate_pornire;
int generatoare[2][NUMAR_GENERATOARE];
int randament[NECERSAR_PORNIRE];









int main()
{



//citire


fin>>nr_gen>>cantitate_pornire;
for(int i = 1; i <= nr_gen; i++)
fin>>generatoare[0][i]>>generatoare[1][i];



//initializare


for (int j = 1; j <= cantitate_pornire; j++)
randament[j] = INFINITY;
randament[0] = 0;





//procesare


for (int i = 1; i <= nr_gen; i++)
for (int j = cantitate_pornire + generatoare[0][i] - 1; j >= generatoare[0][i]; j--)
if (randament[j - generatoare[0][i]] != INFINITY)
if (j >= cantitate_pornire)
if (randament[j - generatoare[0][i]] + generatoare[1][i] < randament[cantitate_pornire])
randament[cantitate_pornire] = randament[j - generatoare[0][i]] + generatoare[1][i];
else;
else
if (randament[j - generatoare[0][i]] + generatoare[1][i] < randament[j])
randament[j] = randament[j - generatoare[0][i]] + generatoare[1][i];




//afisare
int solutie = randament[0];
for (int i = 1; i <= cantitate_pornire; i++)
if (randament[i] != INFINITY && solutie < randament[i])
solutie = randament[i];

fout<<solutie;



return 0;


}