#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int w[10001], p[10001], v1[10001], v2[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 i, cw;
    for(i = 1; i <= n; i++)
    {
        for(cw = 0; cw <= G; cw++)
        {
            v2[cw] = v1[cw];
            if(cw >= w[i])
                v2[cw] = max(v1[cw], v1[cw - w[i]] + p[i]);
        }
        int k;
        for(k = 0; k <= G; k++)
            v1[k] = v2[k];
    }
    g << v2[G];
}
int main()
{
    citire();
    solve();
}