#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int dp[5005][10005];
int main()
{
    int nr_produse, greutate;
    int g, p;
    f >> nr_produse >> greutate;
    for (int i = 1; i <= nr_produse; i++)
    {
        f >> g >> p;
        for (int j = 0; j <= greutate; j++)
            if (g > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - g] + p );
    }
    g << dp[nr_produse][greutate];
    return 0;
}