#include <fstream>

#define MAX_N 5000
#define MAX_G 10000

using namespace std;

//FILE *fin = fopen("rucsac.in", "r");
//FILE *fout = fopen("rucsac.out", "w");

int N, G;

//struct anakin{
//    int Weight, Profit;
//};
//
//anakin Object[MAX_N + 1];

int Sum[MAX_G + 1];

int sol;

int main(){

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

    int i, j;
    int smax;
    int a, b;

    fin>>N>>G;

    Sum[0] = 1;
    smax = 0;

    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;
                if (Sum[j + a] > sol)
                    sol = Sum[j + a];
            }
        }
    }

    fout<<sol - 1;

    fin.close();
    fout.close();
    return 0;
}