Talent Show

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll maxN = 300;
const ll maxW = 1009;

int n, W, w[maxN], t[maxN];
ll dp[maxW];

bool chk (ll x) {
    for (int i = 1; i <= W; i++)
        dp[i] = -INT_MAX;
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        ll value = 1ll * 1000 * t[i] - 1ll * x * w[i];
        for (int j = W; j >= 0; j--) {
            ll nxt = min (W, j + w[i]);
            if (dp[j] != -INT_MAX && dp[nxt] < dp[j] + value)
                dp[nxt] = dp[j] + value;
        }
    }
    return dp[W] >= 0;
}

int main () {
    freopen ("talent.in", "r", stdin);
    freopen ("talent.out", "w", stdout);
    cin >> n >> W;
    for (ll i = 0; i < n; i++)
        cin >> w[i] >> t[i];
    ll l = 0, r = 1000000 * 250 + 1;
    while (r - l > 1) {
        ll mid = l + (r - l) / 2;
        if (chk (mid))
            l = mid;
        else r = mid - 1;
    }
    int res = chk (r) ? r : l;
    cout << res << "\n";
    return 0;
}