#include <fstream>

using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, G, g[5001], p[5001], v[5001][10001];
int main()
{
    cin>>n>>G;
    for (int i=1; i<=n; i++)
        cin>>g[i]>>p[i];

    for (int i = 1; i <= n; i ++)
        for (int w = 1; w <= G; w ++){
            if(g[i] > w)//altfel w - g[i] < 0 si poate da rez dubios ( rezultatul max() ar fi fost oricum prima varianta)
                v[i][w] = v[i-1][w]; //obiectul i nu incape, deci copiez profitul de mai sus
            else
                v[i][w] = max(v[i-1][w], v[i-1][w-g[i]] + p[i]);
        }
   cout<<v[n][G];

}