#include<fstream>
#include<algorithm>
using namespace std;

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

const int maxWeight = 1e4 + 5, NMAX = 5e3 + 5;

int weight[NMAX], price[NMAX], bestPrice[maxWeight];
int N, G;

inline void readData(){

    fin >> N >> G;

    int idx;
    for(idx = 1; idx <= N; ++idx)
        fin >> weight[idx] >> price[idx];
}

inline void getBestPrice(){

    int idx, w;

    for(idx = 1; idx <= N; ++idx)
        for(w = G; w >= weight[idx]; --w)
            bestPrice[w] = max(bestPrice[w], bestPrice[w - weight[idx]] + price[idx]);
    fout << bestPrice[G];
}

int main(){

    readData();
    getBestPrice();
}