#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 = 1; cw <= G; cw++)
        {
            a[i][cw] = a[i - 1][cw];
            if(cw >= w[i])
            a[i][cw] = max(a[i - 1][cw], a[i - 1][cw - w[i]] + p[i]);
        }
     g << a[n][G];
}
int main()
{
    citire();
    solve();
}