#include <iostream>
#include <fstream>
 
using namespace std;
 
int main()
{
    ifstream myFile("rucsac.in");
    int N, G;
    myFile >> N;
    myFile >> G;
    //int w[N], p[N], v[G + 1];
    int w[5000], p[5000], v[10000];
    int i;
    for(i = 0; i < N; i++){
        myFile >> w[i];
        myFile >> p[i];
 
    }
 
    for(i = 0; i <= G; i++){
        v[i] = 0;
    }
 
    for(i = 0; i < N; i++){
        for(int j = G; j > 0; j--){
            if( w[i] <= j ){
                v[j] = max( v[j], v[j - w[i]] + p[i] );
            }
        }
    }
 
    myFile.close();
    ofstream myOtherFile("rucsac.out");
    myOtherFile << v[G];
 
    return 0;
}