#include <iostream>
#include <fstream>
#define nmax 5005
#define g1max 10005
using namespace std;
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int curr[g1max],prev[g1max];
int i,n,j,w[nmax],v[nmax],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(w[i] <= j){
    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];

}
sol=0;
 for(j=1; j<=gmax; j++) sol = max(sol, curr[j]);
    g<<sol<<"\n";
    return 0;
}