#include <fstream>

using namespace std;

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

int n, gr, g[5005], p[5005], i, j;
int c[10005][10005];

int main() {
    cin >> n >> gr;

    for (i = 1; i <= n; ++i)
        cin >> g[i] >> p[i];

    for (i = 1; i <= n; ++i) {
        for (j = 0; j <= gr; ++j) {
            c[i][j] = c[i - 1][j];
            if (g[i] <= j) {
                c[i][j] = max(c[i][j], c[i - 1][j - g[i]] + p[i]);
            }
        }
    }

    cout << c[n][gr] << "\n";

    return 0;
}