#include <fstream>

using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");

int n,gg,castig[1005][5005],c[10005],gr[10005],tot;


int main()
{
    int i,j;
    f>>n>>gg;
    for(i=1;i<=n;i++)
    {
        f>>gr[i]>>c[i];
        tot+=gr[i];
    }
    tot-=gg;
    for(i=1;i<=n;i++)
        for(j=1;j<=tot;j++)
            if(j>=gr[i])
            {

                if(c[i]+castig[i-1][j-gr[i]]>castig[i-1][j])
                    castig[i][j]=c[i]+castig[i-1][j-gr[i]];
                else
                    castig[i][j]=castig[i-1][j];
            }
            else
                castig[i][j]=castig[i-1][j];
    g<<castig[n][tot];
    return 0;
}