#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,g;
struct obj
{
    int pret;
    int greutate;
}v[5005];
long long d[10005];
int sum_max;

int main()
{
    fin>>n>>g;
    for (int i=1;i<=n;i++) {
        fin>>v[i].greutate>>v[i].pret;
    }
    d[0]=1;
    for (int i=1;i<=n;i++) {
        for (int j=g-v[i].greutate;j>=0;j--) {
            if (j>=0 && j+v[i].greutate<10000 && d[j+v[i].greutate]<d[j]+v[i].pret) {
                    d[j+v[i].greutate]=d[j]+v[i].pret;
            }
        }
    }
    for (int i=0;i<=g;i++) if (d[i]>sum_max) sum_max=d[i];
    fout<<sum_max-1;
}