#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int w[5500], p[5500], d[5500][11000], n, gr;

void dostuff(){
    f>>n>>gr;
    for (int i=1; i<=n; i++){
        f>>w[i]>>p[i];
    }
}

void dinamica(){
    int i, cw;
    for (i=1; i<=n; i++){
        for (cw=0; cw<=gr; cw++){
            d[i][cw]=d[i-1][cw];
            if (w[i]<=cw){
                d[i][cw]=max(d[i][cw], d[i-1][cw-w[i]]+p[i]);
            }
        }
    }
}

int main()
{
    dostuff();
    dinamica();
    g<<d[n][gr];
    return 0;
}