#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[5001], P[5001], D[5001][10001];

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

int main()
{

    int i, j;

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

    cin>>N>>G;

    for(i=1;i<=N;++i)
        scanf("%d %d", &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;
}