#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int v[5001],gr[5001],a[10001];
int main()
{
    int n, g, maxi=0, i, j;
    in >> n >>g;
    for(i=1;i<=n;i++)
        in>>gr[i]>>v[i];
    a[0]=1;
    for(i=1;i<=n;++i)
    {
        if(maxi+gr[i]>g)
            maxi=g-gr[i];
        for(j=maxi;j>=0;j--)
            if(a[j])
                {
                    if(j==0)
                        a[j+gr[i]]=max(a[j+gr[i]],a[j]-1+v[i]);
                    else
                        a[j+gr[i]]=max(a[j+gr[i]],a[j]+v[i]);
                }
    maxi=maxi+gr[i];
    }
    maxi=0;
    for(i=g;i>=1;i--)
        if(a[i]>maxi)
            maxi=a[i];
    out<< maxi;
    in.close();
    out.close();
    return 0;
}