#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int d[10001][10001];
int g[10001], p[10001];

int main()
{   int N, G, i, s;
    cin>>N>>G;
    for(i=1; i<=N; i++)
        cin>>g[i]>>p[i];
    for (int i=1; i<=N; i++)
    for (int s=0; s<=G; s++) {
        d[i & 1][s] = d[(i-1) & 1][s];
        if (g[i] <= s)
            d[i & 1][s] = max(d[i & 1][s], d[(i-1) & 1][s-g[i]] + p[i]);
    }
    cout<<d[N & 1][G];
    return 0;
}