#include <fstream>

using namespace std;

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

int maxi(int a, int b){
    if(a>b)return a;
    else return b;
}

int n,G,g[6000], p[6000],d[10010];

int main() {
    in>>n>>G;
    for (int i = 1; i <= n; i++) {
        in>>g[i]>>p[i];
    }

    d[0] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=G; j>=g[i]; j--) {
            if (d[ j-g[i] ]!=0) {
                d[j]=maxi( d[ j-g[i] ]+p[i] , d[j] );
           }
        }
    }

    int mx=0;
    for (int i=1; i<=G; i++) {
        if (mx<d[i]) {
            mx=d[i];
        }
    }
    out<<mx-1;

    return 0;
}