#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[5001], P[5001], D[2][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]);
    int k=0;
    for(i=1;i<=N;++i,k=1-k)
        for(j=0;j<=G;++j)
        {

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

            if(W[i] <= j)
                D[1-k][j] = max(D[k][j], D[k][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%2][G]<<"\n";

    return 0;
}