#include <iostream>
#include <fstream>
using namespace std;

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

const int maxG = 1e4 + 5;
const int maxN = 5e3 + 5;
const int INF = 1e9;

int w[maxN], p[maxN], dp[maxG];

int main () {

    int n, G; fin >> n >> G;

    for(int i = 1; i <= n; ++i)
        fin >> w[i] >> p[i];

    for(int i = 1; i <= G; ++i) dp[i] = -INF;

    dp[0] = 0;

    for(int i = 1; i <= n; ++i)
        for(int j = G-w[i]; j >= 0; --j)
            dp[w[i]+j] = max(dp[w[i]+j], dp[j] + p[i]);

    for(int i = 1; i <= n; ++i)
        dp[i] = max(dp[i-1], dp[i]);

    fout << dp[G] << " ";

    return 0;
}