#include <iostream>
#include <fstream>

using namespace std;

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

int n, gmax, dp[5005][10005], gc, vc;

int main()
{
   f>>n>>gmax;
    for (int i=1;i<=n;i++)
    {
        f>>gc>>vc;
        for (int j=1; j<gc; j++)
            {
                dp[i][j]=dp[i-1][j];
            }
        for (int j=gc;j<=gmax; ++j)
            {
                dp[i][j] = max(dp[i-1][j], dp[i - 1][j - gc] + vc);
            }
    }
    g<<dp[n][gmax];
    return 0;
}