TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

52.8% (19/36)

Submission's AC Ratio

13.9% (33/238)

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≤50,0<N≤1000。

Output Format

顯示最多能夠裝入這些箱子的商品數目。
若找不到能裝入這些箱子的商品,請輸出0。

Sample Input

Sample Input #1:

4 10
30
40
50
25
15
16
30
18
19
20
21
25
24
17


Sample Input #2:

3 9
20
10
10
3
8
3
7
9
3
5
8
5

Sample Output

Sample Output #1:

7


Sample Output #2:

7

Hints

本題保證所有計算過程都不會超出32位元有號整數。

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10