Maximum Non‐Intersecting Tour

Bessie has started a travel agency along the Amoozon river after her daring escape from the farm. On the two banks of the river there are tourist sites. The left bank has n sites and the right bank has m sites. Each site has an integer weight indicating how interesting it is.

There are R bridges (or routes) connecting some sites across the river. Each bridge connects one site on the left bank to one site on the right bank. A bridge is denoted by a pair \((a,b)\) where a is the index of a site on the left bank and b is the index of a site on the right bank. Note that there is no route connecting two sites on the same bank.

A tour is a sequence of tourist sites such that every adjacent pair is connected by a bridge that appears in the input. In order for the tour to be non–intersecting the set of bridges used must not intersect. Two bridges \((a,x)\) and \((b,y)\) are said to intersect if and only if \[ (a < b \text{ and } y < x) \quad \text{or} \quad (b < a \text{ and } x < y) \quad \text{or} \quad (a = b \text{ and } x = y). \] (Recall that all formulas must be written in \(\LaTeX\) format.)

Moreover, the tour must be connected: consecutive bridges must share a common site. In other words, if the tour uses bridges \((a,b)\) and then \((c,d)\), then either b = c (the first bridge is taken in the forward direction from left to right and the second in the forward direction as well) or a = d (the second bridge is traversed in the reverse direction from right to left). In the forward case, it turns out that to avoid intersections one must have \[ a < b \quad \text{and} \quad b d \quad \text{and} \quad b > c. \]

Bessie may start and end at any site on either bank. Your task is to help her select a tour that maximizes the sum of the weights of all visited sites. Note that a tour may consist of a single site (with no bridges used) or of several sites connected by one or more bridges following one of the two patterns described above.

Input constraints: The left bank has n sites, the right bank has m sites, and there are R bridges. All indices are 1–indexed.

inputFormat

The input begins with a line containing three integers n m R.

The next line contains n integers representing the weights of the sites on the left bank (in order from 1 to n).

The following line contains m integers representing the weights of the sites on the right bank (in order from 1 to m).

Then follow R lines. Each of these lines contains two integers a and b indicating that there is a bridge connecting site a on the left bank and site b on the right bank.

outputFormat

Output a single integer which is the maximum possible sum of the weights of the tourist sites visited on a non–intersecting tour.

sample

3 3 3
1 2 3
3 2 1
1 2
2 3
3 1

6