1719 . 商品特賣問題
TopCoder
Tags
Description
在一個年終大拍賣活動中，一家迪化街的商店推出了一個特賣活動，
老闆說只要你花錢買 4 個箱子，第一個箱子最多可裝 30 公斤的商品，第二個箱子最多可裝 40 公斤的商品，
第三個箱子最多可裝 50 公斤的商品，第四個箱子最多可裝 25 公斤的商品。
可以挑選的商品有十種，重量分別是 15, 16, 30, 18, 19, 20, 21, 25, 24, 及 17 公斤。
每一種商品最多只能挑一次，且一種商品不可拆開分到不同箱子中。
假設產品加總的重量小於等於箱子的限定重量就一定裝得下這些產品，
由於每樣產品的售價一樣，因此若挑選能裝入 4 個箱子的商品種類愈多，便表示價值愈高。
請你寫一個程式來算出最多可以裝入這些箱子的商品數目，以便估算是否划算。
Input Format
第一行為兩個整數 $M$ 及 $N$ 以空白區分，
其中 $M$ 表示箱子的個數，而 $N$ 表示商品的種類數。
第二行開始的 $M$ 行各為每一個箱子可容納的最大重量（公斤）。
從第 $M+2$ 行開始的 $N$ 行，則分別表示 $N$ 種商品個別的重量（公斤）。
其中 $0 < M \le 50, 0 < N \le 1000$。
Output Format
顯示最多能夠裝入這些箱子的商品數目。
若找不到能裝入這些箱子的商品，請輸出 0。
Sample Input 1
4 10
30
40
50
25
15
16
30
18
19
20
21
25
24
17
30
40
50
25
15
16
30
18
19
20
21
25
24
17
Sample Output 1
7
Sample Input 2
3 9
20
10
10
3
8
3
7
9
3
5
8
5
20
10
10
3
8
3
7
9
3
5
8
5
Sample Output 2
7
Hints
本題保證所有計算過程都不會超出32位元有號整數。
2024/07/24 Update: Added $\LaTeX$, reformatted, strengthened test data by FHVirus
Problem Source
原TIOJ1719 / TOI2010初選(prob 4)。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |