#include <iostream>
#include <fstream>
#define maxim 5001
#define maximg 10001
using namespace std;
    ifstream f(" rucsac.in");
    ofstream g(" rucsac.out");

int n, G, Pmax;
int w[maxim], p[maxim];
int d[2][maximg];

int main ()
{   f>>n>>G;
    for (int i=1; i<=n; ++i)
        f>>w[i]>>p[i];

    int l=0;
    for (int i=1; i<=n; ++i, l=1-l)
        for (int cw=0; cw<=G; ++cw) {
            d[1-l][cw]=d[l][cw];
        if (w[i]<=cw)
            d[1-l][cw]=max(d[1-l][cw], d[l][cw-w[i]]+p[i]); }
    Pmax=d[l][G];
    g<<Pmax;

    return 0;
}