#include <bits/stdc++.h>
using namespace std;
#define NMAX 10001


int dp[NMAX];

pair<int,int> rucasc[NMAX];
int main(void) {
    ofstream cout("rucsac.out");
    ifstream cin("rucsac.in");
    int n, g;
    cin >> n >> g;
    for(int i = 1;i <= n;i++) {
        cin >> rucasc[i].first >> rucasc[i].second;
    }
    int maxim = -1;
    dp[0] = 1;
    for(int  i = 1;i <= n;i++) {
        for(int s = g; s >= 0; s--) {
            if(dp[s] != 0 && s + rucasc[i].first <= g) {
                dp[s + rucasc[i].first] = max(dp[rucasc[i].first + s], dp[s] + rucasc[i].second );
                maxim = max(maxim, dp[s + rucasc[i].first]);
            }
        }
    }
    cout << maxim  - 1<< endl;
}