10412 - 栅栏的木料

农民John准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状,但是他在木料方面有些问题。当地的杂货储存商扔给John一些木板,而John必须从这些木板中找出尽可能多所需的木料。

  当然,John可以切木板。因此,一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切成3个3英尺的,等等)。John有一把梦幻之锯,因此他在切木料时,不会有木料的损失。

  所需要的木料规格都已经给定。你不必切出更多木料,那没有用。

输入

第1行: N (1 <= N <= 50), 表示提供的木板的数目
第2行到第N+1行: N行,每行包括一个整数,表示各个木板的长度。
第N+2行: R (1 <= R <= 1023), 所需木料的数目
第N+3行到第N+R+1行: R行,每行包括一个整数(1 <= ri <= 128)表示所需木料的长度。

输出

只有一行,一个数字,表示能切除的最多的所需木料的树木。当然,并不是任何时候都能切出所有所需木料。

样例

输入

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

输出

7

提示

Fence Rails Burch, Kolsad, and Schrijvers Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but he's having a problem with the rails. The local lumber store has dropped off boards of varying lengths; Farmer John must create as many of the rails he needs from the supplied boards.

Of course, Farmer John can cut the boards, so a 9 foot board can be cut into a 5 foot rail and a 4 foot rail (or three 3 foot rails, etc.). Farmer John has an ideal saw', so ignore the kerf' (distance lost during sawing); presume that perfect cuts can be made.

The lengths required for the rails might or might not include duplicates (e.g., a three foot rail and also another three foot rail might both be required). There is no need to manufacture more rails (or more of any kind of rail) than called for the list of required rails.

PROGRAM NAME: fence8 INPUT FORMAT Line 1: N (1 <= N <= 50), the number of boards
Line 2..N+1: N lines, each containing a single integer that represents the length of one supplied board
Line N+2: R (1 <= R <= 1023), the number of rails
Line N+3..N+R+1: R lines, each containing a single integer (1 <= ri <= 128) that represents the length of a single required fence rail

SAMPLE INPUT (file fence8.in) 4 30 40 50 25 10 15 16 17 18 19 20 21 25 24 30

OUTPUT FORMAT A single integer on a line that is the total number of fence rails that can be cut from the supplied boards. Of course, it might not be possible to cut all the possible rails from the given boards. SAMPLE OUTPUT (file fence8.out) 7

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题