#include <fstream>
using namespace std;
ifstream ka("rucsac.in");
ofstream ki("rucsac.out");
int w[5001],p[5001],d[2][10001],n,g;
int maxim(int t,int k)
{
    if(t>=k)
    return t;
    return k;
}
int main()
{
    ka>>n>>g;
    for(int i=1;i<=n;i++)
    ka>>w[i]>>p[i];
    for(int j=1;j<=n;j++)
    {
        for(int cw=1;cw<=g;cw++)
        {
            d[1][cw]=d[0][cw];
            if(w[j]<=cw)
            d[1][cw]=maxim(d[1][cw],d[0][cw-w[j]]+p[j]);
        }
        for(int cw=1;cw<=g;cw++)
        {
            d[0][cw]=d[1][cw];
        }
    }
    ki<<d[1][g];
}