#include <bits/stdc++.h>

using namespace std;
int n,g,p[5005],w[5005],d[2][10005],G,i,l;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
    fin >> n >> G;
    for(i=1;i<=n;i++)
    fin >> w[i] >> p[i];
    for(i=1;i<=n;i++,l=1-l)
    {
        for(g=0;g<=G;g++)
        {
            d[1-l][g]=d[l][g];
            if(w[i]<=g )
                d[1-l][g]=max(d[l][g],p[i]+d[l][g-w[i]]);
        }
    }
    fout << d[l][G];
    return 0;
}