#include <bits/stdc++.h>

using namespace std;

const int INF = 1 >> 30;
const int G_MAX = 10001;

int N, G;
int dp[2][G_MAX];
vector <int> g, p;

void read() {
    ifstream fin("rucsac.in");

    fin >> N >> G;
    g.resize(N + 1); p.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        fin >> g[i] >> p[i];
    }

    fin.close();
}

void solve() {
    int current = 1, last = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= G; ++j) {
            dp[current][j] = dp[last][j];
            if (g[i] <= j) {
                dp[current][j] = max(dp[current][j], dp[last][j - g[i]] + p[i]);
            }
        }

        last = (last == 0) ? 1 : 0;
        current = (current == 1) ? 0 : 1;
    }
}

void write() {
    ofstream fout("rucsac.out");

    int maxim = -INF;
    for (int j = 0; j <= G; ++j) {
        maxim = max(maxim, dp[0][j]);
        maxim = max(maxim, dp[1][j]);
    }

    fout << maxim;

    fout.close();
}

int main() {
    read();
    solve();
    write();
    return 0;
}