#include <iostream>
#include <fstream>

using namespace std;

short N, G, W[501], P[500], D[501][101];

short max(short a, short b)
{
    return a > b ? a : b;
}

int main()
{

    short i, j;

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    cin>>N>>G;

    for(i=1;i<=N;++i)
        cin>>W[i]>>P[i];

    for(i=1;i<=N;++i)
        for(j=0;j<=G;++j)
        {

            D[i][j] = D[i-1][j];

            if(W[i] <= j)
                D[i][j] = max(D[i][j], D[i-1][j-W[i]] + P[i]);

        }

  /*  for(i=1;i<=N;i++)
    {

        for(j=0;j<=G;j++)
            cout<<D[i][j]<<" ";

        cout<<endl;
    }*/
    cout<<D[N][G]<<"\n";

    return 0;
}