#include <iostream>
#include <fstream>

using namespace std;

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

int A0[10001], A1[10001], *P0, *P1;
int g[5001], v[5001];

int main()
{
    int n, G;
    f >> n >> G;
    P0 = A0;
    P1 = A1;
    for(int i = 1; i <= n; i++)
        f >> g[i] >> v[i];


    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= G; j++)
        {
            if(g[i] > j)P1[j] = P0[j];
            else P1[j] = max(P0[j], v[i] + P0[j - g[i]]);
        }
        swap(P0, P1);
    }
    out << A0[G];
    return 0;
}