有两个柱子 A 和 B 并排摆放。每个柱子上有 $N$ 个把手，这些把手从下到上依次编号为 1 到 $N$。每个柱子上的把手都挂有 0 个或更多的香蕉。$A_i$ 表示挂在柱子 A 的第 $i$ 个把手上的香蕉数量，$B_j$ 表示挂在柱子 B 的第 $j$ 个把手上的香蕉数量。这些值是 0 到 $10^9$ 之间的整数。
猴子可以用两只手抓住不同柱子上的把手。注意，猴子不会同时抓住同一个柱子上的两个把手。此外，猴子并非可以抓住任意把手。猴子可以抓住的一对把手可以用 $(x, y)$ 表示，这意味着它可以同时抓住柱子 A 的第 $x$ 个把手和柱子 B 的第 $y$ 个把手。此时，猴子可以吃掉这两个把手上剩余的所有香蕉。显而易见，一旦吃掉，香蕉就会消失。这样的有序对共有 $M$ 个。
起初，猴子从可以抓住的一对把手中的某一个位置出发。当猴子当前位于 $(x, y)$ 位置时，若要移动到另一个可以抓住的把手对 $(x', y')$，必须满足 $x < x', y = y'$ 或者 $x = x', y < y'$。
猴子当然希望尽可能多地吃香蕉。给定关于可抓住的把手的信息以及这些把手上挂着的香蕉数量，请编写一个程序，计算猴子最多能吃到的香蕉数量。
实现细节
你需要实现以下函数：
long long int max_bananas(vector<int> A, vector<int> B,
vector< pair<int, int> > P)- 该函数将被调用且仅被调用一次。
- $A$ 的长度为 $N$，$A[i]$ 是挂在柱子 A 第 $i+1$ 个把手上的香蕉数量 ($0 \le i \le N-1$)。
- $B$ 的长度为 $N$，$B[i]$ 是挂在柱子 B 第 $i+1$ 个把手上的香蕉数量 ($0 \le i \le N-1$)。
- $P$ 的长度为 $M$。如果 $(x, y)$ 包含在 $P$ 中，则猴子可以同时抓住柱子 A 的第 $x$ 个把手和柱子 B 的第 $y$ 个把手。此时，它可以吃掉这两个把手上剩余的所有香蕉。保证不会给出重复的有序对。
- 该函数必须根据输入信息计算并返回猴子能吃到的最多香蕉数量。
提交的源代码的任何部分都不应执行输入输出函数。
数据范围
- $1 \le N \le 500\,000$
- $1 \le M \le 500\,000$
- $M \le N^2$
- $0 \le A_i \le 10^9$ ($1 \le i \le N$)
- $0 \le B_i \le 10^9$ ($1 \le i \le N$)
- 参数 $P$ 给出的有序对 $(x, y)$ 均不相同，且满足 $1 \le x \le N, 1 \le y \le N$。
子任务
- (11分)
- $M \le 16$
- (42分)
- $M \le 5\,000$
- (97分)
- 无额外限制。
评分标准
只有当 max_bananas 函数返回的香蕉数量与正确答案一致时，该数据才会被判定为正确。
请注意，每个子任务的得分是该子任务所有数据得分中的最小值。
样例
- 考虑 $N = 3, M = 3, A = [2, 3, 1], B = [3, 2, 4], P = [(1, 1), (2, 1), (1, 3)]$ 的情况，如下图所示。
评测机将调用以下函数：
max_bananas([2, 3, 1], [3, 2, 4], [(1, 1), (2, 1), (1, 3)])从 $(1, 1)$ 位置出发，移动到 $(1, 3)$ 位置，总共可以吃掉 $2 + 3 + 4 = 9$ 个香蕉，没有比这吃得更多的方法。因此，max_bananas 函数应返回 9。
说明
该样例满足所有子任务的条件。
Sample grader
Sample grader 按以下格式接收输入：
- Line 1: $N \ M$
- Line 2: $A[0] \ A[1] \ \dots \ A[N - 1]$
- Line 3: $B[0] \ B[1] \ \dots \ B[N - 1]$
- Line $3 + i$ ($1 \le i \le M$): $P[i - 1].\text{first} \ P[i - 1].\text{second}$
Sample grader 按以下格式输出：
- Line 1: 函数
max_bananas返回的值
请注意，Sample grader 可能与实际评测时使用的评测机不同。