#include <fstream>

using namespace std;

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

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

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