#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int dp[10001], we[5001], v[5001], n, i, j, G;

int main()
{
    f >> n >> G;

    for(i = 1; i <= n; ++ i)
        f >> we[i] >> v[i];

    for(i = 1; i <= n; ++ i)
        for(j = G; j >= we[i]; j --)
          dp[j] = max(dp[j], dp[j - we[i]] + v[i]);

    g << dp[G];

    f.close();
    g.close();

    return 0;
}