题目描述

有 $N$ 种编号为 $1$ 到 $N$ 的糖果。第 $i$ 种糖果有 $A_i$ 个。

有 $M$ 个编号为 $1$ 到 $M$ 的孩子。现在要给这些孩子分糖果。分配时需满足以下所有条件：

• 孩子 $i$ 对于任意一种糖果，最多只能拿 $B_i$ 个。
• 孩子 $i$ 拿到的糖果总数不超过 $C_i$。

在满足上述条件的前提下，求能分给孩子们的糖果总数的最大值。

输入格式

输入按以下格式从标准输入给出。

$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

输出

11

样例 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

输出

211

说明/提示

限制条件

• $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}$
• 输入的所有值均为整数。

样例解释 1

可以如下分配糖果：

• 孩子 $1$ 分别获得糖果 $1,2,3$ 各 $1,1,1$ 个。
• 孩子 $2$ 分别获得糖果 $1,2,3$ 各 $0,2,1$ 个。
• 孩子 $3$ 分别获得糖果 $1,2,2$ 各 $1,2,2$ 个。

由 ChatGPT 4.1 翻译