Después de escapar de la granja, Bessie ha decidido empezar una agencia de viajes en el rio Amoozon. Hay varios sitios turisticos situados a ambos lados del rio, cada uno tiene asociado un valor entero indicando cuan interesante es.

Los sitios turisticos estan conectados por rutas que cruzan el rio (i.e., no hay rutas conectando dos sitios del mismo lado del rio). Bessie quiere diseñar un tour para sus clientes y necesita su ayuda. Un tour es una secuencia de sitios turisticos con sitios adyacentes conectados por una ruta. En orden de servir mejor a sus clientes, ella quiere encontrar la ruta que maximiza la suma de los valores asociados a cada sitio visitado.

De todas formas, Bessie puede estar recorriendo un grupo de tours al mismo tiempo. Es importante que dos rutas en un tour no se intersequen. Dos rutas, ~(a - x)~ y ~(b - y)~ se intersecan si y solo si (~a < b~ y ~y < x~), (~b < a~ y ~x < y~) o (~ a = b~ y ~x = y~).

Ayude a Bessie a encontrar el mejor tour para su agencia. Bessie puede empezar y terminar en cualquier sitio y lado del rio Amoozon.

Entrada

Una linea con tres enteros separados por espacios, ~N~ ~(1 \leq N \leq 40000)~, ~M~ ~(1 \leq M \leq 40000)~ y ~R~ ~(0 \leq R \leq 100000)~, indicando el numero de sitios en el lado izquierdo del rio, el numero de sitios en el lado derecho y el numero de rutas respectivamente.

~N~ lineas, donde la i-ésima linea contiene un solo entero ~L_i~ ~(0 \leq L_i \leq 40000)~, indicando el valor del i-ésimo sitio turistico en el lado izquierdo del rio.

~M~ lineas, donde la i-ésima linea contiene un solo entero ~R_i~ ~(0 \leq R_i \leq 40000)~, indicando el valor del i-ésimo sitio turistico en el lado derecho del rio.

~R~ lineas, conteniendo dos enteros separados por espacios, ~I~ ~(1 \leq I \leq N)~ y ~J~ ~(1 \leq J \leq M)~ indicando una ruta bidireccional entre el sitio ~I~ en el lado izquierdo y ~J~ en el lado derecho.

Salida

Una linea conteniendo un solo entero que es la suma maxima de valores del tour.

Ejemplo de Entrada

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

Ejemplo de Salida

8

Explicación del ejemplo: Hay tres sitios al lado izquierdo del rio Amoozon con valores ~1~, ~1~ y ~5~. Hay dos sitios al lado derecho del rio Amoozon con valores ~2~ y ~2~. Hay cuatro rutas conectando sitios a ambos lados del rio.

El tour mas óptimo va desde el sitio ~1~ en la izquierda, sitio ~1~ en la derecha, y terminas en el sitio ~3~ en la izquierda.Tales sitios tienen valores de ~1~, ~2~ y ~5~, dando un total de ~8~.