#include <fstream>

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

struct obiect {
    int gr, cost;
};

int dp[2][10001];
int n, G;
obiect Y[5001];

int main() {
    int i, j;
    int a, b;

    fin >> n >> G;
    for (i = 1; i <= n; ++i)
        fin >> Y[i].gr >> Y[i].cost;

    for (i = 1; i <= n; ++i)
        for (j = 1; j <= G; ++j) {
            a = b = 0;
            if (j >= Y[i].gr)
                a = dp[(i + 1) % 2][j - Y[i].gr] + Y[i].cost;

            b = dp[(i + 1) % 2][j];

            dp[i % 2][j] = max(a, b);
        }

    fout << dp[n % 2][G] << '\n';

    return 0;
}