#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace  std;
typedef long long ll;

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> val(N), wt(N);
    for(int i = 0; i < N; i++) {
        cin >> val[i] >> wt[i];
    }
    vector<int> dp(W + 5, -2e9);
    dp[W] = 0;

    for(int weight = W; weight >= 0; weight--) {
        for(int i = 0; i < N; i++) {
            if(weight - wt[i] >= 0) {
                dp[weight - wt[i]] = max(dp[weight - wt[i]], dp[weight] + val[i]);
            }
        }
    }
    int result = -2e9;
    for(int i = 0; i <= W; i++) {
        result = max(result, dp[i]);
    }
    if(result == -2e9) result = 0;
    cout << result << endl;
    return 0;
}
/*
 3 8
 3 30
 4 50
 5 60

 140: 12
 139 = inf
 138 = inf

 110: 9
 90: 8
 80: 7
 60: 5
 50: 4
 30: 3
 */