d078. P_6_9 大賣場免費大搬家

Content

你抽中了大賣場的周年慶的抽獎活動，在不超過總重量 $W$ 的限制下，你可任意挑選商品免費帶走。現場一共 $n$ 項商品，每項商品有它的重量與價值，每項商品只可以選或不選，不可以拆開只拿一部份。請計算可以獲得的最大價值總和。

Input

第一行有兩個正整數 $n$ 與 $W$。

第二行有 $n$ 個正整數，依序代表商品的重量。

第三行有 $n$ 個正整數，依序代表對應 n 項商品的價值。同一行數字間以空白隔開。

$n \le 100$， $W$ 與各商品重量及價值皆不超過 $10^5$。

Output

最大價值總和。

Sample Input #1

7 10
3 4 2 3 3 6 5
5 5 2 4 4 5 6

Sample Output #1

Sample Input #2

5 14
1 2 3 4 5
3 2 4 4 4

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

Hint ：

前5筆測資$n \le 20$

Tags:

ch6

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」