Monkey

Two pillars A and B stand side by side. Each pillar has $N$ handles, numbered 1 through $N$ from bottom to top. Each pillar has zero or more bananas hanging on it. $A_i$ is the number of bananas hanging on handle $i$ of pillar A, and $B_j$ is the number of bananas hanging on handle $j$ of pillar B. These values are integers between 0 and $10^9$ inclusive.

The monkey can grab handles on different pillars with its two arms. Note that it never grabs two handles on the same pillar. Also, the monkey cannot grab just any handle. A pair of handles the monkey can grab is written as $(x, y)$, meaning it can grab handle $x$ of pillar A and handle $y$ of pillar B at the same time. The monkey then eats all bananas remaining on those two handles. As expected, a banana once eaten is gone. There are $M$ such ordered pairs in total.

Initially the monkey starts at one of the grabbable pairs of handles. When the monkey is at $(x, y)$, it can move to another grabbable pair $(x', y')$ only if $x < x'$ and $y = y'$, or $x = x'$ and $y < y'$.

Naturally, the monkey wants to eat as many bananas as possible. Given the grabbable handles and the numbers of bananas hanging on them, write a program that finds the maximum number of bananas the monkey can eat.

• $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)$
• Every ordered pair $(x, y)$ given as the input P is distinct, and satisfies $1 \le x \le N$, $1\le y \le N$.