public class ClassicProblem {

    final int N = 80; // Max number of objects, Max weight
    long[] dp;

    public long maximalValue(int[] cnt, int[] w, int[] v, int limit)
    {
        int n = cnt.length;
        long ret = 0;

        // First we sort them by (value / weight), from small to large
        for(int iteration = 1; iteration <= n; iteration ++)
            for(int i = 0; i < n-1; i++)
                if((long) v[i] * w[i+1] > (long) v[i+1] * w[i])
                {
                    int t = w[i]; w[i] = w[i+1]; w[i+1] = t;
                    t = v[i]; v[i] = v[i+1]; v[i+1] = t;
                    t = cnt[i]; cnt[i] = cnt[i+1]; cnt[i+1] = t;
                }

        int M = N * N * N;
        dp = new long[M+1];
        for(int i = 1; i <= M; i++)
            dp[i] = -1000000000000000000L;
        // take < M of {0 .. i-1}, take some i, take all of {i+1 .. n}
        for(int i = 0; i < n; i++)
        {
            int s = Math.min(N, cnt[i]);
            for(int j = 1; ; j *= 2)
            {
                int x = Math.min(s, j);
                for(int k = M; k >= x * w[i]; k--)
                    dp[k] = Math.max(dp[k], dp[k-x*w[i]] + 1L*v[i]*x);
                s -= x;
                if(s == 0)
                    break;
            }
        }

        for(int i = 0; i <= Math.min(M, limit); i++)
        {
            int remain = limit - i;
            long cur = dp[i];
            for(int j = n-1; j >= 0; j--)
            {
                int take = Math.min(remain / w[j], cnt[j] - Math.min(cnt[j], N));
                remain -= w[j] * take;
                cur += (long)v[j] * take;
            }
            ret = Math.max(ret, cur);
        }
        return ret;
    }

}