#include <fstream>
using namespace std;

int Gmax,n,g[5001],C[5001],vizitat[10001][5001],G,Cost[5001];
ifstream fin("rucsac.in");
ofstream gout("rucsac.out");

int main(){


    fin >> n >> Gmax;
    for(int i=1;i<=n;i++)
    fin >> g[i] >> C[i];

         for(G=1;G<=Gmax;G++)
        for(int i=1;i<=n;i++)
            if(g[i]<=G && ! vizitat[G-g[i]][i])
                if(Cost[G] < C[i] + Cost[G-g[i]]){
                      Cost[G] = C[i] + Cost[G-g[i]];
                        for(int k=1;k<=n;k++)
                            vizitat[G][k] = vizitat[G-g[i]][k];
                            vizitat[G][i] = 1;
                }
gout << Cost[Gmax];
return 0;
}