6030: 安排工作以达到最大收益
[Creator : ]
Description
有一些工作:difficulty[i] 表示第 $i$ 个工作的难度,profit[i] 表示第 $i$ 个工作的收益。
现在我们有一些工人。worker[i] 是第 $i$ 个工人的能力,即该工人只能完成难度小于等于 worker[i] 的工作。
每一个工人都最多只能安排一个工作,但是一个工作可以完成多次。
举个例子,如果 $3$ 个工人都尝试完成一份报酬为 $1$ 的同样工作,那么总收益为 $3$。如果一个工人不能完成任何工作,他的收益为 $0$。
我们能得到的最大收益是多少?
现在我们有一些工人。worker[i] 是第 $i$ 个工人的能力,即该工人只能完成难度小于等于 worker[i] 的工作。
每一个工人都最多只能安排一个工作,但是一个工作可以完成多次。
举个例子,如果 $3$ 个工人都尝试完成一份报酬为 $1$ 的同样工作,那么总收益为 $3$。如果一个工人不能完成任何工作,他的收益为 $0$。
我们能得到的最大收益是多少?
Input
第一行输入一个正整数 $n\ (0 \leq n \leq 10,000)$,表示工作份数;
第二、三行分别输入 $n$ 个正整数,表示这 $n$ 份工作的难度和收益;
第四行输入一个正整数 $m\ (0 \leq m \leq 10,000)$,表示工人数量;
第五行输入 $m$ 个正整数,表示这 $m$ 个工人的能力;
其中 $0≤n≤10,000,\ 0≤m≤10,000,\ 0≤difficulty[i],\ profit[i],\ worker[i]≤100,000$。
第二、三行分别输入 $n$ 个正整数,表示这 $n$ 份工作的难度和收益;
第四行输入一个正整数 $m\ (0 \leq m \leq 10,000)$,表示工人数量;
第五行输入 $m$ 个正整数,表示这 $m$ 个工人的能力;
其中 $0≤n≤10,000,\ 0≤m≤10,000,\ 0≤difficulty[i],\ profit[i],\ worker[i]≤100,000$。
Output
输出一个数,表示最大的收益。
Sample 1 Input
5
2 4 6 8 10
10 20 30 40 50
4
4 5 6 7
Sample 1 Output
100
Sample 2 Input
4
18 0 8 0
27 30 12 24
4
24 0 22 24
Sample 2 Output
120