#include <bits/stdc++.h>
#define k 5001
using namespace std;
int w[k],p[k];
int a[10001];
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int N,G,i,cw,j;
    f>>N>>G;
    for(i=1;i<=N;i++)
        f>>w[i]>>p[i];
    for(i=w[1];i<=G;i++)
        a[i]=p[1];
    for(i=2;i<=N;i++)
    {
        for(cw=G;cw>=1;cw--)
            if(cw-w[i]>=0)
                a[cw]=max(a[cw],a[cw-w[i]]+p[i]);


    }

    g<<a[G];
    f.close();
    g.close();
}