9717 - Route Design

从农场逃出后，贝茜决定在亚马逊河沿岸开一家旅行社。河两岸分布着多个旅游景点，每个景点都有一个整数值表示其趣味性。

旅游景点通过横跨河流的路线相连（即不存在连接同一河岸两侧景点的路线）。贝西需要为顾客设计旅游路线，现需你的协助。旅游路线是由相邻景点通过路线连接而成的序列。为了给顾客提供最佳服务，她希望找到使所有访问景点价值总和最大的路线。

然而，贝西可能同时运营多条此类线路。因此，同一线路中的两条路线绝不能重叠相交。两条路线（a <-> x）和（b <-> y）相交当且仅当（a < b 且 y < x）或（b < a 且 x < y）或（a = b 且 x = y）。

帮助贝茜为她的旅行社找到最佳旅游路线。贝茜可在亚马逊河两岸的任意站点开始或结束行程。

第一行：三个以空格分隔的整数N（1<=N<=40,000）、M（1<=M<=40,000）和R（0<=R<=100,000），表示分别表示河流左岸的站点数量、河流右岸的站点数量以及路线数量

第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行：一个整数，表示一次旅行中可达到的最大值之和。

USACO