#include <fstream>
using namespace std;

const int MAX_SIZE = 5005, MAX_WEIGHT = 10005;
int price[MAX_SIZE];
int weight[MAX_SIZE];
int sol[MAX_WEIGHT];

void citire(int &n, int &g){
    ifstream in("rucsac.in");
    in>>n>>g;
    for(int i=1;i<=n;i++)
        in>>weight[i]>>price[i];
    in.close();
}

void rezolva(int n, int g){
    for(int i=1;i<=n;i++)
        for(int j=g;j>=weight[i];j--)
            sol[j] = max(sol[j], price[i] + sol[ j - weight[i] ]);
}

void afiseaza(int g){
    ofstream out("rucsac.out");
    out<<sol[g]<<"\n";
    out.close();
}

int main()
{
    int n, g;
    citire(n, g);
    rezolva(n, g);
    afiseaza(g);
    return 0;
}