4072. 大航海

【题目描述】

当你的船队进入了一个河道，河道的两边布满繁华的港口，你和你的手下都非常渴望马上进入这些港口进行贸易，以获得利润，但是流域的管理者却告诉你在他们的地盘航行必须遵守他们的法令。河道左岸的N个港口被编号为L1，L2，…，LN，河道右岸的M个港口被编号为R1，R2，…，RM。法令规定如果你进入过左岸（右岸）的某个港口Li(Ri)，你就不能再进入编号为L1，L2，…，Li（R1，R2，…，Ri）的港口。法令还规定了P条航道，每条航道(i，j)表示你可以从Li港驶到Rj港，或者从Rj港驶到Li港。其他港口之间的航行都是不被允许的。一开头你可以选择停靠在任意一个港口，并且任何时候都可以离开这个流域。一旦离开了这个流域，你就不能再回来了。

给定进入每个港口能获取的利润，就能够迅速估计你最多能够获得的总利润是多少。

【输入格式】

每个输入文件只包含一组数据。

每个文件的第1行包含三个正整数N,M,P。1≤N，M≤10 000，0≤P≤500 000。

以下N行，每行一个非负整数，第i行表示在港口Li能获得的利润。以下M行，每行一个非负整数，第i行表示在港口Ri能获得的利润。所有利润的总和不会超过10^9。

再下来P行，每行两个整数i,j，表示一个航道。

【输出格式】

输出一行，表示能够获得的最大的总利润。

【样例输入1】

3 3 5
5
0
10
10
10
0
1 2
3 1
2 2
2 3
3 2

【样例输出1】

30

【样例输入2】

3 3 0
8
9
10
5
6
7

【样例输出2】

10

【提示】