#include <fstream>
std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");
int dp[2][10001];
int weight[5005];
int price[5005];
int main()
{
    int G, n;
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
    {
        fin >> weight[i] >> price[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= G; j++)
        {
            if(j < weight[i])
            {
                dp[i % 2][j] = dp[(i - 1) % 2][j];
            }
            else
            {
                dp[i % 2][j] = std::max(dp[(i - 1) % 2][j], price[i] + dp[(i - 1) % 2][j - weight[i]]);
            }
        }
    }
    fout << dp[n % 2][G];
    return 0;
}