题目描述

逃离农场后，${Bessie }$决定在 ${Amoozon }$河沿岸开一家旅行社。河的两岸有几个旅游景点，每个景点都有一个整数值，表示旅游景点的有趣程度。

旅游景点由过河的路线连接（即，没有路线将地点与河流同一侧的地点连接起来）。${Bessie }$想为她的客户设计一次旅行，需要您的帮助。旅游是一系列旅游景点，相邻景点通过路线连接。为了最好地服务于她的客户，她希望找到最大化与每个访问站点相关联的值的总和的路线。

但是，${Bessie }$可能会同时进行其中的几个巡回演出。因此，重要的是旅行中没有两条路线

相交。两条路线 ${(a <-> x) }$和 ${(b <-> y) }$相交当且仅当 ${(a < b and y < x) }$或 ${(b < a and x < y) }$或 ${(a = b and x = y ）}$。

帮助 ${Bessie }$为她的代理机构找到最好的巡演。${Bessie }$可以在 ${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)}$。

输入格式

第 ${1 }$行：三个空格分隔的整数 ${N (1 <= N <= 40,000)}$、${M (1 <= M <= 40,000) }$和 ${R (0 <= R <= 100,000) }$表示

分别为河流左侧站点数量、河流右侧站点数量和路线数量。

${Lines 2..N+1：}$第${(i+1)}$行有一个整数，${L_i (0 <= L_i <= 40,000)，}$表示河流左侧第${i}$个旅游景点的价值。

第${N+2..N+M+1}$行：第${(i+N+1)}$行有一个整数，${R_i (0 <= R_i <= 40,000)，}$表示右边第${i}$个旅游景点的值河边。

第 ${N+M+2..N+M+R+1 }$行：每行包含两个空格分隔的整数 ${I (1 <= I <= N) }$和 ${J (1 <= J <= M)，}$表示存在双向位于河流左侧的站点 ${I }$和位于河流右侧的站点 ${J }$之间的路线。

输出格式

第 ${1 }$行：一个整数，表示游览中可达到的最大总和。

样例

输入样例

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

输出样例

8

提示

${Amoozon }$左侧有 ${3 }$个站点，值为 ${1}$、${1 }$和 ${5}$。${Amoozon }$右侧有两个站点，值为 ${2 }$和 ${2}$。有 ${4 }$条路线连接河流两侧的站点。

最佳游览从左侧的站点 ${1}$、右侧的站点 ${1 }$到左侧的站点 ${3 }$结束。它们分别具有值 ${1}$、${2 }$和 ${5，}$给出行程的总价值 ${8}$。