#include <bits/stdc++.h>

#define NMAX 5000
#define GMAX 10000

using namespace std;

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

const int INFINIT = 5000 * 10000;

int w[NMAX + 1];
int v[NMAX + 1];

int dp[GMAX + 1];

int main()
{
    int N, G;
    fin >> N >> G;

    for(int i = 1; i <= N; i++){
        fin >> w[i] >> v[i];
    }

    for(int i = 1; i <= N; i++){
        for(int gr = G; gr >= 1; gr--){
            if(gr - w[i] >= 0){
                dp[gr] = max(dp[gr], dp[ gr - w[i] ] + v[i]);
            }
        }

    }

    fout << dp[G] << "\n";

    return 0;
}