#include <iostream>
#include <fstream>
# define nmax 5005
# define greutatemaxima 50005

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int i,n,j,w[nmax],v[nmax],curr[greutatemaxima],prev[greutatemaxima],gmax,max1,sol;
int main()
{f>>n;
f>>gmax;

for(i=1;i<=n;i++){f>>w[i]>>v[i];}
for(j=1; j<=gmax; j++)
        curr[j] = 0, prev[j] = 0;
         prev[ w[1] ] = v[1];
for(i=2;i<=n;i++)
for(j=1;j<=gmax;j++){
curr[j]=prev[j];
    if(j>=w[i]){
    curr[j]=max(curr[j],v[i]);
    if(prev[j-w[i]]!=0){curr[j]=max(curr[j],prev[j-w[i]]+v[i]);}
    }
    for(j=1;j<gmax;j++)
    prev[j]=curr[j];
}
for(j=1;j<=gmax;j++)
sol=max(sol,curr[j]);
g<<sol;

    return 0;
}