#include <fstream>

using namespace std;

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

int n, gmax, dp[2][10010], w[5010], p[5010], b = 1;

int main()
{
    f >> n >> gmax;
    for(int i=1; i<=n; i++) f >> w[i] >> p[i];
    for(int i=1; i<=n; i++)
    {
        b = !b;
        for(int cw=1; cw<=gmax; cw++)
            {   if(cw - w[i] >= 0) dp[b][cw] = max(dp[!b][cw], dp[!b][cw-w[i]]+p[i]);
                else dp[b][cw] = dp[!b][cw];
            }
    }
    g << dp[b][gmax] << '\n';
    return 0;
}