分数: 800 点
问题陈述
有 N 零食种类编号 1 通过 N。 我们有 A_i 零食片 i.
有 M 儿童编号 1 通过 M。 我们会将零食分发给这些孩子。 这里,必须满足以下所有条件。
-
对于每种零食,儿童 i 最多获得 B_i 那种。
-
儿童 总共 i 最多获得 C_i 件零食。
求在这些条件下可以分发给孩子们的零食的最大总数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{12}
- 1 \leq B_i \leq 10^7
- 1 \leq C_i \leq 10^{12}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M C_1 C_2 \cdots C_M
输出
打印答案。
样本输入 1
3 3 2 5 5 1 2 2 5 3 5
示例输出 1
11
零食的最优分配如下。
-
儿童 总共 1 得到 1, 1, 1 一块零食 1, 2, 3。
-
儿童 总共 2 得到 0, 2, 1 块零食 1, 2, 3。
-
儿童 总共 3 得到 1, 2, 2 块零食 1, 2, 3。
示例输入 2
10 6 3 54 62 64 25 89 1 47 77 4 1 17 10 29 95 17 32 40 90 27 50 9
示例输出 2
211