题目描述

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

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

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

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

帮助 $\red{Bessie }$为她的代理机构找到最好的巡演。$\red{Bessie }$可以在 $\red{Amoozon }$两侧的任何地点开始和结束。

河左岸有$\red{n}$个点，右岸有$\red{m}$个点，各有权值。有$\red{R}$条跨河的桥，求一条不交叉的路径使得点权和最大。

$\red{(a <-> b) }$与 $\red{(x <-> y) }$交叉指$\red{(a < b and y < x) or (b < a and x < y) or (a = b and x = y)}$。

输入格式

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

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

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

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

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

输出格式

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

样例

输入样例

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

输出样例

8

提示

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

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