#include <iostream>
#include <fstream>
using namespace std;
int n,gmax,cmax[1001],g[1001],c[1001],i,j,s;
bool use[1001][1001];
int main()
{
    ifstream f("rucsac.in");
    f>>n>>gmax;
    for(i=1;i<=n;i++)
        f>>g[i]>>c[i];
    for(i=1;i<=gmax;i++)
        cmax[i]=-1;
    for(s=1;s<=gmax;s++)
        for(i=1;i<=n;i++)
            if(g[i]<=s&&cmax[s-g[i]]!=-1&&!use[s-g[i]][i]&&cmax[s-g[i]]+c[i]>cmax[s])
            {
                cmax[s]=cmax[s-g[i]]+c[i];
                for(j=1;j<=n;j++)
                    use[s][j]=use[s-g[i]][j];
                use[s][i]=true;
            }
    int max1=0;
    for(i=1;i<=gmax;i++)
        max1=max(max1,cmax[i]);
    ofstream g("rucsac.out");
    g<<max1;
    return 0;
}