Problem Description

Solve the 0/1 knapsack problem. The 0/1 knapsack problem is defined as follows:

• There are $ N $ items, and the $i\ (1≦i≦N)$th item has a value $ v_i $ and a weight $ w_i $.
• There is a knapsack with a maximum capacity of $ W $.
• Determine the maximum total value of items that can be packed into the knapsack such that the total weight does not exceed $ W $. Note that each item can only be selected once.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains an integer $N\ (1≦N≦200)$ representing the number of items and an integer $ W(1≦W≦10^9) $ representing the maximum weight capacity of the knapsack, separated by a space.
• The next $ N $ lines contain the information for each item. The $ i(1≦i≦N) $th line contains an integer $v_i\ (1≦v_i≦10^9)$ representing the value of the $ i $th item and an integer $w_i\ (1≦w_i≦10^9)$ representing the weight of the $ i $th item, separated by a space.
• At least one of the following conditions holds:
• $ N≦30 $
• For all $ i(1≦i≦N) $, $ 1≦w_i≦1000 $
• For all $ i(1≦i≦N) $, $ 1≦v_i≦1000 $

Output Format

Output the maximum possible total value that can be achieved to the standard output.

Sample Input and Output

Sample Input #1

3 10
15 9
10 6
6 4

Sample Output #1

16

Sample Input #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

Sample Output #2

3673016420

Sample Input #3

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

Sample Output #3

3657162058

Sample Input #4

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

Sample Output #4

1686

Notes/Hints

Partial Points

This problem has partial scoring. The full score is 100 points.

• If you solve the dataset where $ N≦30 $ correctly, you will be awarded 34 points.
• If you solve the dataset where $ N≦200 $ and for all $ i(1≦i≦N) $, $ 1≦w_i≦1000 $ correctly, you will be awarded an additional 33 points.
• If you solve the dataset where $ N≦200 $ and for all $ i(1≦i≦N) $, $ 1≦v_i≦1000 $ correctly, you will be awarded an additional 33 points.

Sample Explanation 1

Choosing the 2nd and 3rd items results in a total weight of 10 and a total value of 16, achieving the maximum value. This input-output example satisfies the constraints of datasets 1, 2, and 3, and is used for scoring all datasets.

Sample Explanation 2

This input-output example only satisfies the constraints of dataset 1, and is not used for scoring datasets 2 and 3.

Sample Explanation 3

This input-output example does not satisfy the constraints of dataset 3, and is not used for scoring dataset 3.

Sample Explanation 4

This input-output example does not satisfy the constraints of dataset 2, and is not used for scoring dataset 2.

见题面 Input 部分

见题面 Output 部分