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.

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.

A single integer indicating the maximum sum of values attainable on a tour.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > February > Gold