#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

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

int N, G;
int w[NMAX + 2], p[NMAX + 2];
int dp[GMAX + 2];

int main() {
    cin >> N >> G;

    for(int i = 1; i <= N; i++) {
        cin >> w[i] >> p[i];
    }

    for(int i = 1; i <= N; i++) {
        for(int g = G; g >= w[i]; g--) {
            dp[g] = max(dp[g], dp[g - w[i]] + p[i]);
        }
    }

    cout << dp[G] << '\n';
    return 0;
}