원숭이

두 개의 기둥 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'$이어야 한다.

원숭이는 당연히도 바나나를 최대한 많이 먹고 싶어한다. 잡을 수 있는 손잡이들에 대한 정보와 이 손잡이들에 매달린 바나나의 수에 대한 정보가 주어졌을 때, 원숭이가 가장 많이 먹을 수 있는 바나나의 수를 구하는 프로그램을 작성하라.

• $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$을 만족한다.