#include <fstream>
using namespace std;

int N, G, W[5000], V[5000], T[2][10001];

void change(){
    int i;

    for (i=0; i<=G; i++)
        T[0][i]=T[1][i];
}

int main(){
    int i, j;

    //ifstream fin ("knapsack.in");
    ifstream fin ("rucsac.in"); //infoarena
    fin >> N >> G;
    for (i=0; i<N; i++)
        fin >> W[i] >> V[i];
    fin.close();

    for (i=0; i<=N; i++)
        T[i][0]=0;
    for (i=0; i<=G; i++)
        T[0][i]=0;

    for (i=0; i<N; i++){
        for (j=0; j<=G; j++)
            T[1][j]=((W[i]>j)?(T[0][j]):(max(T[0][j], V[i]+T[0][j-W[i]])));
        change();
    }

    //ofstream fout ("knapsack.out");
    ofstream fout ("rucsac.out"); //infoarena
    fout << T[1][G] << '\n';
    fout.close();

    return 0;
}