#include <bits/stdc++.h>
using namespace std;
#define nmax 5000
#define grmax 10000
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int v[nmax+5],gr[nmax+5],optim[grmax+5];

int main()
{
    int n,gmax,sol=0;
    f>>n>>gmax;
    for(int i=1;i<=n;++i)
        f>>gr[i]>>v[i];
    optim[0]=0;
    for(int i=1;i<=n;++i)
        for(int j=gmax-gr[i];j>=0;--j)
            if(optim[j+gr[i]]<optim[j]+v[i]){
                optim[j+gr[i]]=optim[j]+v[i];
                if(optim[j+gr[i]]>sol)sol=optim[j+gr[i]];
            }
    g<<sol;
}