#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int w[10001], p[10001], a[5002][10001];
int n, G;
void citire()
{
    f >> n >> G;
    int i;
    for(i = 1; i <= n; i++)
        f >> w[i] >> p[i];

}
void solve()
{
    int cw, i;
    for(i = 1; i <= n; i++)
        for(cw = w[i]; cw <= G; cw++)
            a[i][cw] = max(a[i - 1][cw], a[i - 1][cw - w[i]] + p[i]);
}
int main()
{
    citire();
    solve();
    g << a[n][G];
}