#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define cin fin
#define cout fout
int n, G;
struct val{
    int g, p;
} v[5005];
int maxp[5005][1005];
int dp (int k, int g){
    if (k == n) return 0;
    if (maxp[k][g] == -1){
        maxp[k][g] = dp(k + 1, g);
        if (g + v[k].g <= G){
            maxp[k][g] = max(maxp[k][g], v[k].p + dp(k + 1, g + v[k].g));
        }
    } return maxp[k][g];
}
int main(){
    cin >> n >> G;
    for (int i = 0; i < n; ++i){
        cin >> v[i].g >> v[i].p;
    }
    memset(maxp, -1, sizeof(maxp));
    cout << dp(0, 0) << endl;
    return 0;
}