Description

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.

Input Format

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$.

Output Format

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.

4 10
8 9
5 8
4 6
2 5
4 13
8 9
5 8
4 6
2 5
16 75594681
393216 5533
2 77
32768 467
29360128 407840
112 68
24576 372
768 60
33554432 466099
16384 318
33554432 466090
2048 111
24576 350
9216 216
12582912 174768
16384 295
1024 76
-1 -1

14
19
1050650

Hint

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