#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
short N,G,i,j;
int a[2][10001];
int W[5001],P[5001];

int main()
{
    f>>N>>G;
    for (i=1;i<=N;i++)
    f>>W[i]>>P[i];
    for (i=1;i<=N;i++)
    {
        for (j=0;j<=G;j++)
        {
            a[1][j]=a[0][j];
            if(W[i]<=j)
                a[1][j] = max(a[1][j], a[0][j-W[i]]+P[i]);
        }
        for (j=0;j<=G;j++)
        a[0][j]=a[1][j];
    }
    g<<max(a[0][G],a[1][G]);
    f.close();g.close();
    return 0;
}