#include <fstream>

#define MAX_N 5000
#define MAX_G 10000

using namespace std;

int N, G;
int Sum[MAX_G + 1];
int sol;

int main(){

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

    int i, j;
    int a, b;

    fin>>N>>G;

    Sum[0] = 1;

    for (i = 1; i <= N; i++) {
        fin>>a>>b;
        for (j = G - a; j >= 0; j--) {
            if (Sum[j + a] < Sum[j] + b) {
                Sum[j + a] = Sum[j] + b;
            }
        }
    }

    for (i = 1; i <= G; i++) {
        if (Sum[i] > sol)
            sol = Sum[i];
    }

    fout<<sol - 1;

    return 0;
}