← 返回题目列表

AtCoder · arc125_e

E. 小吃

中文机器翻译题面 查看原题

分数: 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