#include <fstream>
#include <vector>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int g;
vector <int> m,p;
vector <vector <int> > x;

void read()
{
    int n;
    cin >> n >> g;

    m.resize(n); p.resize(n);
    for (int i=0; i<n; i++)
        cin >> m[i] >> p[i];
}

void form()
{
    x.resize(1);
    x[0].resize(g+1);
    fill(x[0].begin(),x[0].end(),0);
    for (int i=1; i<m.size(); i++)
        x.push_back(x[0]);
}

void solve()
{
    for (int i=0; i<x.size(); i++)
        if (m[i]<=0) x[i][0]=p[i];
    for (int i=m[0]; i<x[0].size(); i++)
        x[0][i]=p[0];
    for (int i=1; i<x.size(); i++)
        for (int j=1; j<=g; j++)
        {
            x[i][j]=x[i-1][j];
            if (m[i]<=j)
                x[i][j]=max(x[i][j],x[i-1][j-m[i]]+p[i]);
        }
}

void write()
{
    cout << x[m.size()-1][g];
}

main()
{
    read();
    form();
    solve();
    write();
}