#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    fstream myFile;
    myFile.open("rucsac.in");
    int N, G;
    myFile >> N;
    myFile >> G;
    int w[N], p[N], v[G + 1], i;
    for(i = 0; i < N; i++){
        myFile >> w[i];
        myFile >> p[i];
        //cout << ">" << i + 1 << ". " << w[i] << " " << p[i] << '\n';
    }

    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();
    myFile.open("rucsac.out");
    myFile << v[G];

    return 0;
}