Talent show knapsack

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

namespace cp {
   #define REP(i, x) for (int i = 0; i < (x); i++)
   #define pb push_back
   #define ins insert
   #define sz(x) (int)(x).size()
   #define all(x) (x).begin(), (x).end()
   typedef long long ll;
   typedef vector<int> vi;

   void setUsacoIO(string name) {
       ios::sync_with_stdio(false);
       cin.tie(0);
       freopen((name + ".in").c_str(), "r", stdin);
       freopen((name + ".out").c_str(), "w", stdout);
   }
}
using namespace cp;

const int MXN = 255;
const int MXW = 250 * 1000 + 5;
int n, W;
int w[MXN], t[MXN];
int dp[MXW];

int main() {
    setUsacoIO("talent");

    cin >> n >> W;
    REP (i, n) {
        cin >> w[i] >> t[i];
    }

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int j = 0; j < n; j++) {
        for (int i = MXW - 1; i >= 0; i--) {
            if (dp[i] == -1) continue;
            if (i + w[j] < MXW) {
                dp[i + w[j]] = max(dp[i + w[j]], dp[i] + t[j]);
            }
        }
    }

    int ret = 0;
    for (int i = W; i < MXW; i++) {
        ret = max(ret, (dp[i] * 1000) / i);
    }

    cout << ret << endl;

    return 0;
}