Route Design

Bessie has opened a travel agency along the Amoozon river. Tourist sites lie on both banks of the river: there are $N$ sites on the left bank and $M$ sites on the right bank, and each site has an integer value describing how interesting it is.

Every route crosses the river, connecting a site on the left bank to a site on the right bank; no route connects two sites on the same bank. A tour is a sequence of sites in which every pair of adjacent sites is joined by a route, so a tour alternates between the two banks. Bessie may begin and end a tour at any site on either bank. The value of a tour is the sum of the values of the distinct sites it visits, and she wants a tour of maximum value.

Because several tours may run at the same time, no two routes used by a single tour may intersect. Number the left-bank sites $1$ to $N$ from one end, and the right-bank sites $1$ to $M$ from the same end. A route joining left site $a$ to right site $x$ and a route joining left site $b$ to right site $y$ intersect exactly when at least one of these holds: $a < b$ and $y < x$; or $b < a$ and $x < y$; or $a = b$ and $x = y$.

Find the maximum value of a tour.

• The first line contains three integers $N$, $M$, and $R$ ($1 \le N \le 40000$, $1 \le M \le 40000$, $0 \le R \le 100000$): the number of left-bank sites, the number of right-bank sites, and the number of routes.
• Each of the next $N$ lines contains one integer $L_i$ ($0 \le L_i \le 40000$): the value of the $i$-th left-bank site.
• Each of the next $M$ lines contains one integer $R_i$ ($0 \le R_i \le 40000$): the value of the $i$-th right-bank site.
• Each of the next $R$ lines contains two integers $I$ and $J$ ($1 \le I \le N$, $1 \le J \le M$): a route between left-bank site $I$ and right-bank site $J$.

• Print one integer: the maximum value attainable by a single tour.

In the first example the left bank has three sites with values $1$, $1$, and $5$, the right bank has two sites with values $2$ and $2$, and there are four routes. The best tour starts at left site $1$, goes to right site $1$, and ends at left site $3$; their values $1 + 2 + 5$ total $8$.