#include <iostream>
#include<fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int MAX_N=5001;
const int MAX_G=10000;
struct t_object{
int greutate;
int profit;

};
int memo[MAX_N][MAX_G];
int dp_profit(int idx,int capacitate,t_object objs[]){

if (idx==0)
    return 0;
if (capacitate==0)
    return 0;
if (memo[idx][capacitate]!=0){

    return memo[idx][capacitate];
}
if (objs[idx].greutate>capacitate){

    memo[idx][capacitate]=dp_profit(idx-1,capacitate,objs);
    return memo[idx][capacitate];
}
int profit1=dp_profit(idx-1,capacitate,objs);
int new capacitate=capacitate-objs[idx].greutate;
int profit2=objs[idx].profit+dp_profit(idx-1,new_capacitate,objs);

memo[idx][capacitate]=max(profit1,profit2);
return memo[idx][capacitate];


}


int main()
{
int nr_elem;
int max_gr;
t_object objs[MAX_N];
fin>>nr_elem;
fin>>max_gr;
for (int i=1;i<=nr_elem;i++){
    int greutate;
    int profit;
    fin>>greutate;
    fin>>profit;
    t_oject obs={greutate,profit};
    objs[i]=obj;

}
fout<<dp_profit(nr_elem,max_gr,objs);
return 0;

}