#include <fstream>

using namespace std;

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

const int nmax=5000, dmax=10000;
int v[nmax+1], d[dmax+1], c[dmax+1];

int main () {
    int n, s;
    fin>>n>>s;

    for (int i=1; i<=n; i++) {
        fin>>v[i]>>c[i];
    }
    d[0]=1;
    for (int i=1; i<=n; i++) {
        for (int j=s; j>=v[i]; j--) {
            if (d[j-v[i]]!=0 && c[i]+d[s-v[i]]>=d[i]) {
                 d[j]=c[i]+d[j-v[i]];
            }
        }
    }
     while (d[s]==0) {
        s--;
    }
    fout<<d[s]-2<<"\n";
    return 0;
}