#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 5e3;
const int GMAX = 1e4;

int dp[GMAX + 1];

struct object {
    int price;
    int weight;
} v[NMAX + 1];

int main() {
    ifstream fin( "rucsac.in" );
    ofstream fout( "rucsac.out" );
    int n, g, i, j;
    fin >> n >> g;
    for ( i = 1; i <= n; i ++ )
        fin >> v[i].weight >> v[i].price;
    for ( i = 1; i <= n; i ++ ) {
        for ( j = g; j >= v[i].weight; j -- ) {
            dp[j] = max( dp[j], dp[j - v[i].weight] + v[i].price );
        }
    }
    fout << dp[g];
    return 0;
}