[HNOI2007]梦幻岛宝珠

给你 $N$ 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 $W$，且总价值最大，并输出最大的总价值。

输入格式

输入文件中包含多组数据，每组数据的格式如下。

第一行是两个正整数 $n$ 和 $W$，分别表示宝石的数目和最多能带走的宝石重量。

接下来的 $n$ 行，每行有两个正整数 $\mathit{weight}_i$ 和 $\mathit{value}_i$，分别表示第 $i$ 颗宝石的重量和价值。同一行的两个正整数之间用空格隔开。

最后一组数据的后面有两个 $-1$，表示文件的结束。这两个 $-1$ 并不代表一组数据，你不需对这组数据输出结果。

输出格式

对于输入的每组数据，输出一个整数 $C$，表示小 P 最多能带走的宝石的总价值。

每个结果整数 $C$ 单独占一行。

样例输入

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

样例解释

第一组数据中 $W=10$，选取重量为 $5$ 和 $4$ 的两颗宝石，总重量 $9\le 10$，总价值为 $8+6=14$。

第二组数据中 $W=13$，选取重量为 $5, 4, 2$ 的三颗宝石，总重量 $11\le 13$，总价值为 $8+6+5=19$。

数据范围

• $1\le n\le 100$；
• $1\le W\le 2^{30}$；
• $1\le \mathit{weight}_i\le 2^{30}$，且保证 $\mathit{weight}_i$ 能写成 $a\times 2^b$ 的形式，其中 $1\le a\le 10$，$0\le b\le 30$；
• $0\le \mathit{value}_i\le 2^{30}$；
• 输入文件中数据的组数不超过 $20$，且保证答案 $C$ 不会超过 $2^{30}$。

来源与许可

本题为 HNOI 2007 试题「梦幻岛宝珠」，题面与测试数据整理自 BZOJ 1190。

样例 1

输入

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