TFG

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <limits>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const int ms = 1e6 + 10;
const int mc = 1010;

long long dp[ms];
int c[mc], lim[mc];

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    int n, s;
    std::cin >> n >> s;
    for(int i = 0; i < n; i++) {
        int w, cost;
        std::cin >> w >> cost;
        c[w] = std::max(c[w], cost);
    }
    for(int i = 1; i < mc; i++) {
        lim[i] = std::max(lim[i], lim[i-1]);
        if(c[i] <= lim[i]) {
            continue;
        }
        lim[i+1] = std::max(lim[i+1], c[i]);
        for(int j = i; j < ms; j++) {
            dp[j] = std::max(dp[j], dp[j-i] + c[i]);
        }
        for(int j = 2; i * j < mc; j++) {
            lim[i*j] = std::max(lim[i*j], c[i] * j);
        }
    }
    for(int i = 1; i < ms; i++) {
        assert(dp[i] >= dp[i-1]);
    }
    long long ans = 0;
    for(int i = 1; i < mc; i++) {
        int freq = std::max(0, (s - ms) / i - 2);
        while(s - freq * i >= ms) {
            freq++;
        }
        ans = std::max(ans, (long long) freq * c[i] + dp[s - freq * i]);
    }
    std::cout << ans << '\n';
}