#include <fstream>

int main()
{
    short n, g;

    std::ifstream in("rucsac.in");
    in >> n >> g;

    short w[n], p[n];
    for (short i = 0; i < n; i++)
        in >> w[i] >> p[i];
    in.close();

    int dp[g]{};
    for (short i = 0; i < n; i++)
        for (short j = g - 1; w[i - 1] <= j; j--)
            dp[j] = std::max(dp[j], dp[j - w[i - 1] + p[i - 1]]);

    std::ofstream out("rucsac.out");
    out << dp[g - 1];
    out.close();

    return 0;
}