#include <iostream>
#include <fstream>
#define NUM 5005
int Optim[NUM*2];
int gr[NUM];
int val[NUM];
int n, G, sol;
using namespace std;
int maxim(int a, int b)
{
    return (a > b) ? a : b;
}
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f >> n >> G;
    for(int i = 0; i < n; ++i)
        f >> gr[i] >> val[i];

    for( int i = 0; i < n; ++i)
        for( int j = G; j >= gr[i]; --j)
            Optim[j] = maxim(Optim[j], Optim[j - gr[i]] + val[i]);
    sol = Optim[G];
    g << sol;
    f.close();
    g.close();
}