#include <fstream>

using namespace std;

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

int c[10005],gr[10005],castig[1004][5004],n,gg,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])
            {
                castig[i][j]=max(c[i]+castig[i-1][j-gr[i]],castig[i-1][j]);
            }
            else
                castig[i][j]=castig[i-1][j];
    g<<castig[n][tot];
    return 0;
}