19346번 - Knapsack 다국어

문제

To fit the best stuff in a sack
with limits on what you can pack
recursion will do
if memoized too
but DP puts less on the stack.

You are given a classic knapsack problem: a set of elements $(w_1, v_1), \dots, (w_n, v_n)$ and a capacity $W$. Solve

$$\max_{\substack{S \subseteq [n]\\\sum_{i\in S} w_i \leq W}} \sum_{i \in S} v_i\text{.}$$

Here, $[n]$ is the list of integers from 1ドル$ through $n$.

You are guaranteed that 0ドル \leq n \leq 500,ドル 0ドル \leq w_i \leq W \leq 10^{17},ドル and 0ドル \leq v_i \leq 10^{16}$. Furthermore, you are guaranteed that the $w_i$ have been "smoothed" as described in the next paragraph.

A problem instance complying with the above bounds is constructed. Then a randomizing filter is applied to the problem instance as follows: Let $B$ be the weight of the element of maximum weight. Now the following update is applied to each weight:

$$ w_i \leftarrow \min (w_i + \mbox{rand}(\lfloor .05 B \rfloor), W) $$

Here $\mbox{rand}(A)$ is a function that generates a uniform random integer in $[0, A-1]$. This process is applied only to the $w_i,ドル not to $W$ or any of the other values.

입력

The first line contains the two space-separated integers $n$ and $W$. Each of the next $n$ lines contains two space-separated integers $w_i$ and $v_i$. The element weights were generated as described above. First the items are chosen in compliance with all the bounds. Then the smoothing algorithm is applied. The result is what your program will receive as input.

출력

Output one line with the value of the given knapsack problem instance.

제한

힌트