#include<fstream>
using namespace std;
int dp[10001], v[5001], we[5001], n, G, i, j;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    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];
    return 0;
}