题目描述

有 $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$、$2$、$3$ 号零食。

• 第二个孩子分别得到 $0$、$2$、$1$ 个 $1$、$2$、$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