#include <bits/stdc++.h>
using namespace std;
int dp[10005], v[5005], we[5005], 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;
}