Talent Show

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <numeric>
#include <iomanip>
#include <regex>
using namespace std;
#define pii pair<long long , long long>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const long long dl[2] = {1, -1};
const long long MOD = 1e9 + 7;
const long long MAX = 255;

long long n, w;
long long weight[MAX], talent[MAX];
long long dp[1005];

bool check(long long cur){
    for(long long i = 0; i <= w; i++){
        dp[i] = -2e9;
    }
    dp[0] = 0;
    for(long long i = 0; i < n; i++){
        long long tmp = 1000 * talent[i] - cur * weight[i];
        for(long long j = w; j >= 0; j--){
            if(dp[j] == -2e9){
                continue;
            }
            if(dp[min(w, j + weight[i])] < dp[j] + tmp){
                dp[min(w, j + weight[i])] = dp[j] + tmp;
            }
        }
    }
    if(dp[w] >= 0){
        return true;
    }
    else{
        return false;
    }
}

int main() {
    freopen("talent.in", "r", stdin);
    freopen("talent.out", "w", stdout);
    FAST;
    cin >> n >> w;
    for(long long i = 0; i < n; i++){
        cin >> weight[i] >> talent[i];
    }
    long long lo = 0, hi = 250000001;
    while(lo < hi){
        long long mid = (lo + hi) / 2 + 1;
        if(check(mid)){
            lo = mid;
        }
        else{
            hi = mid - 1;
        }
    }
    cout << lo << "\n";
}