#P1528. 切蛋糕

    ID: 519 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>搜索贪心深度优先搜索,DFS剪枝

切蛋糕

题目描述

Facer今天买了 nn 块蛋糕,不料被信息组中球球等好吃懒做的家伙发现了,没办法,只好浪费一点来填他们的嘴巴。他答应给每个人留一口,然后量了量每个人口的大小。Facer 有把刀,可以切蛋糕,但他不能把两块蛋糕拼起来,但是他又不会给任何人两块蛋糕。现在问你,facer 怎样切蛋糕,才能满足最多的人。(facer 的刀很强,切的时候不会浪费蛋糕)。

输入格式

第一行 nn,facer 有 nn 个蛋糕。接下来 nn 行,每行表示一个蛋糕的大小。再一行一个数 mm,为信息组的人数,然后 mm 行,每行一个数,为一个人嘴的大小。(1n50(1\le n\le 501m1024) 1\le m\le 1024)

输出格式

一行,facer最多可以填多少张嘴巴。

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

 

7