경로 설계

Bessie가 Amoozon 강을 따라 여행사를 열었다. 강의 양쪽 기슭에 관광지가 있는데, 왼쪽 기슭에는 $N$개, 오른쪽 기슭에는 $M$개의 관광지가 있다. 각 관광지에는 얼마나 흥미로운지를 나타내는 정수 값이 매겨져 있다.

모든 노선(route)은 강을 가로질러 왼쪽 기슭의 관광지와 오른쪽 기슭의 관광지를 잇는다. 같은 기슭에 있는 두 관광지를 잇는 노선은 없다. 여행 경로(tour)는 관광지의 수열로, 인접한 두 관광지는 항상 하나의 노선으로 연결된다. 따라서 여행 경로는 두 기슭을 번갈아 오간다. 여행 경로는 어느 기슭의 어느 관광지에서든 시작하고 끝낼 수 있다. 여행 경로의 값은 방문한 서로 다른 관광지들의 값의 합이며, Bessie는 값이 최대가 되는 여행 경로를 찾고자 한다.

여러 여행 경로가 동시에 진행될 수 있으므로, 하나의 여행 경로에서 사용하는 어떤 두 노선도 서로 교차해서는 안 된다. 왼쪽 기슭의 관광지에 한쪽 끝에서부터 $1$부터 $N$까지, 오른쪽 기슭의 관광지에도 같은 쪽 끝에서부터 $1$부터 $M$까지 번호를 매긴다. 왼쪽 관광지 $a$와 오른쪽 관광지 $x$를 잇는 노선과 왼쪽 관광지 $b$와 오른쪽 관광지 $y$를 잇는 노선은, 다음 중 하나가 성립할 때 정확히 교차한다: $a < b$ 이고 $y < x$; 또는 $b < a$ 이고 $x < y$; 또는 $a = b$ 이고 $x = y$.

여행 경로가 가질 수 있는 최대 값을 구하여라.

• 첫째 줄에 세 정수 $N$, $M$, $R$이 주어진다 ($1 \le N \le 40000$, $1 \le M \le 40000$, $0 \le R \le 100000$). 각각 왼쪽 기슭의 관광지 수, 오른쪽 기슭의 관광지 수, 노선의 수이다.
• 이어지는 $N$개의 줄에는 각각 정수 $L_i$가 주어진다 ($0 \le L_i \le 40000$). 왼쪽 기슭 $i$번째 관광지의 값이다.
• 이어지는 $M$개의 줄에는 각각 정수 $R_i$가 주어진다 ($0 \le R_i \le 40000$). 오른쪽 기슭 $i$번째 관광지의 값이다.
• 이어지는 $R$개의 줄에는 각각 두 정수 $I$와 $J$가 주어진다 ($1 \le I \le N$, $1 \le J \le M$). 왼쪽 기슭 $I$번 관광지와 오른쪽 기슭 $J$번 관광지를 잇는 노선이다.

• 하나의 여행 경로로 얻을 수 있는 최대 값을 정수 하나로 출력한다.

첫 번째 예시에서 왼쪽 기슭에는 값이 각각 $1$, $1$, $5$인 세 관광지가 있고, 오른쪽 기슭에는 값이 각각 $2$, $2$인 두 관광지가 있으며, 노선은 네 개이다. 최적의 여행 경로는 왼쪽 $1$번에서 출발해 오른쪽 $1$번을 거쳐 왼쪽 $3$번에서 끝나며, 값 $1 + 2 + 5$를 더해 총 $8$이 된다.