问题描述

请解决0/1背包问题。0/1背包问题是指以下问题：

• 有N个物品，第i (1≤i≤N)个物品的价值为$v_i$，重量为$w_i$。
• 有一个承重量为W的背包。
• 在总重量不超过W的情况下，选择一组物品放入背包中，使得总价值最大。同一个物品只能选择一次。

---

输入

输入从标准输入中按以下格式给出：

$N$ $W$ $v_1$ $w_1$ $v_2$ $w_2$ : $v_N$ $w_N$

• 第1行是由一个空格分隔的整数$N(1≤N≤200)$和整数$W(1≤W≤10^9)$，分别表示物品的数量和背包的承重量。
• 第2行到第N行是每个物品的信息。其中第i行（1≤i≤N）是由一个空格分隔的整数$v_i(1≤v_i≤10^9)$和整数$w_i(1≤w_i≤10^9)$，分别表示第i个物品的价值和重量。
• 须满足以下三个条件的至少一个："$N≤30$", "$1≤w_i≤1000$ (1≤i≤N)", "$1≤v_i≤1000$ (1≤i≤N)"。

---

子任务

本问题有子任务得分。满分为100分。

• 对数据集1（满足$N≤30$）正确解答将获得34分。
• 对数据集2（满足$N≤200$且对所有的$i(1≤i≤N)$满足$1≤w_i≤1000$）正确解答，除了上述分数外，还可额外获得33分。
• 对数据集3（满足$N≤200$且对所有的$i(1≤i≤N)$满足$1≤v_i≤1000$）正确解答，除了上述分数外，还可额外获得33分。

---

输出

输出结果以以下格式打印到标准输出：

在第一行输出能达到的最大总价值。不要忘记换行符。

---

输入示例1

3 10
15 9
10 6
6 4

输出示例1

16

选择第2个和第3个物品时，总重量为10，总价值为16，可以达到最大价值。此输入输出示例将用于检查所有数据集。

---

输入示例2

30 499887702
128990795 137274936
575374246 989051853
471048785 85168425
640066776 856699603
819841327 611065509
704171581 22345022
536108301 678298936
119980848 616908153
117241527 28801762
325850062 478675378
623319578 706900574
998395208 738510039
475707585 135746508
863910036 599020879
340559411 738084616
122579234 545330137
696368935 86797589
665665204 592749599
958833732 401229830
371084424 523386474
463433600 5310725
210508742 907821957
685281136 565237085
619500108 730556272
88215377 310581512
558193168 136966252
475268130 132739489
303022740 12425915
122379996 137199296
304092766 23505143

输出示例2

3673016420

此输入输出示例仅用于检查数据集1。

---

输入示例3

10 2921
981421680 325
515936168 845
17309336 371
788067075 112
104855562 96
494541604 960
32007355 161
772339969 581
55112800 248
98577050 22

输出示例3

3657162058

此输入输出示例不符合数据集3的限制，因此不适用于数据集3的评分。

---

输入示例4

10 936447862
854 810169801
691 957981784
294 687140254
333 932608409
832 42367415
642 727293784
139 870916042
101 685539955
853 243593312
369 977358410

输出示例4

1686

此输入输出示例不符合数据集2的限制，因此不适用于数据集2的评分。