[USACO13FEB] Route Design G

After escaping from the farm, Bessie has decided to start a travel agency along the Amoozon river. There are several tourist sites located on both sides of the river, each with an integer value indicating how interesting the tourist site is. Tourist sites are connected by routes that cross the river (i.e., there are no routes connecting a site with a site on the same side of the river). Bessie wants to design a tour for her customers and needs your help. A tour is a sequence of tourist sites with adjacent sites connected by a route. In order to best serve her customers she wants to find the route that maximizes the sum of the values associated with each visited site. However, Bessie may be running several of these tours at the same time. Therefore it's important that no two routes on a tour intersect. Two routes (a <-> x) and (b <-> y) intersect if and only if (a < b and y < x) or (b < a and x < y) or (a = b and x = y). Help Bessie find the best tour for her agency. Bessie may start and end at any site on either side of the Amoozon. 河左岸有n个点，右岸有m个点，各有权值。有R条跨河的桥，求一条不交叉的路径使得点权和最大。 (a <-> b) 与 (x <-> y) 交叉指(a < b and y < x) or (b < a and x < y) or (a = b and x = y)。

\* Line 1: Three space separated integers N (1 <= N <= 40,000), M (1 <= M <= 40,000), and R (0 <= R <= 100,000) indicating respectively the number of sites on the left side of the river, the number of sites on the right side of the river, and the number of routes. \* Lines 2..N+1: The (i+1)th line has a single integer, L\_i (0 <= L\_i <= 40,000), indicating the value of the ith tourist site on the left side of the river. \* Lines N+2..N+M+1: The (i+N+1)th line has a single integer, R\_i (0 <= R\_i <= 40,000), indicating the value of the ith tourist site on the right side of the river. \* Lines N+M+2..N+M+R+1: Each line contains two space separated integers I (1 <= I <= N) and J (1 <= J <= M) indicating there is a bidirectional route between site I on the left side of the river and site J on the right side of the river.

\* Line 1: A single integer indicating the maximum sum of values attainable on a tour.

3 2 4 
1 
1 
5 
2 
2 
1 1 
2 1 
3 1 
2 2 

8 

There are three sites on the left side of the Amoozon with values 1, 1, and 5. There are two sites on the right side of the Amoozon with values 2 and 2. There are four routes connecting sites on both sides of the river. The optimal tour goes from site 1 on the left, site 1 on the right, and ends at site 3 on the left. These respectively have values 1, 2, and 5 giving a total value of the trip of 8.