#include <iostream>
#include <fstream>

int greutate[5001];
int valoare[5001];

int dp[10001][2];

int main() {
    int N, G;
    int i, j;

    std::ifstream fin("rucsac.in");

    fin >> N >> G;
    for (i = 1; i <= N; i++) {
        fin >> greutate[i];
        fin >> valoare[i];
    }

    fin.close();

    for (i = 1; i <= N; i++)
        for (j = 1; j <= G; j++) {
            if (greutate[i] <= j)
                dp[j][i % 2] = std::max(valoare[i] + dp[j - greutate[i]][(i + 1) % 2], dp[j][(i + 1) % 2]);
            else
                dp[j][i % 2] = dp[j][(i + 1) % 2];
        }

    std::ofstream fout("rucsac.out");
    fout << dp[G][N % 2];
    fout.close();

    return 0;
}