大賣場免費大搬家 (AP325 P-6-9)

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

輸入格式

第一行有兩個正整數 \(n\) 與 \(W\)。第二行有 \(n\) 個正整數，依序代表商品的重量；第三行有 \(n\) 個正整數，依序代表對應 \(n\) 項商品的價值。同一行數字間以空白隔開。

限制

• \(1 \le n \le 100\)。
• \(W\) 與各商品的重量及價值皆為不超過 \(10^5\) 的正整數。

輸出格式

輸出最大價值總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

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

範例輸出 1

14

範例輸入 2

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

範例輸出 2

15

範例說明

範例一：選擇第 \(1\)、\(2\)、\(4\) 三項，重量為 \(3+4+3=10\)，價值為 \(5+5+4=14\)。

範例二：選擇第 \(1\)、\(3\)、\(4\)、\(5\) 四項，重量為 \(1+3+4+5=13\)，價值為 \(3+4+4+4=15\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 P-6-9，第 180 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。