#include <iostream>
#include <fstream>

using namespace std;

const int nmax=5001, gmax=10001;
int v[nmax][2], dp[2][gmax];

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int main()
{
    int n, g;
    fin >> n >> g;
    for(int i=1; i<=n; i++)
        fin >> v[i][0] >> v[i][1];
    for(int i=1; i<=n; i++)
        for(int w=1; w<=g; w++)
        {
            if(v[i%2][0]>w)
                dp[i%2][w]=dp[(i-1)%2][w];
            else
                dp[i%2][w]=max(dp[(i-1)%2][w], dp[(i-1)%2][w-v[i][0]] + v[i][1]);
        }
    fout << dp[n][g];
    return 0;
}