P3188 [HNOI2007] Dream Island Orbs

You are given $n$ gems, each with a weight and a value. Choose some of these gems so that the total weight does not exceed $W$, and the total value is maximized. Output the maximum total value.

The input contains multiple test cases. Each test case is formatted as follows: The first line contains two positive integers $n$ and $W$, representing the number of gems and the maximum total weight you can carry. The next $n$ lines each contain two positive integers $w_i, v_i$, representing the weight and value of the $i$-th gem. After the last test case, there are two $-1$ indicating the end of file. These two $-1$ do not represent a test case, and you should not output a result for them. The number of test cases in the input file does not exceed $20$.

For each test case, output an integer $c$, the maximum total value of the gems you can carry. Print each integer $c$ on a separate line.

### Constraints For $100\%$ of the testdata, $1\le n \le 100$, $1\le W,w_i,v_i \le 2^{30}$. It is guaranteed that each $w_i$ can be written as $a \times 2^b\space (a,b \in \mathbb N)$ with $a \leq 10$, $b \leq 30$, and the answer does not exceed $2^{30}$. Translated by ChatGPT 5