题目描述

给你两个数组 $a$ 和 $b$

数组 $a$ 的大小是 $n$，里面的元素是 a[1], a[2], ..., a[n];

数组 $b$ 的大小是 $m$，里面的元素是 b[1], a[2], ..., b[m];

现在你需要从 $a$ 和 $b$中各取 1 个数，记为 $a[i]$ 和 $b[j]$。

但现在有一些 $a[i]$ 和 $b[j]$ 的组合是不能同时选取的。

我们希望在满足条件的情况下 $a[i]+b[j]$ 的和最大，请输出这个最大和。

输入格式

输入包括若干行

第 1 行包括 3 个整数 $n$, $m$, $L$, 分别表示数组 $a$ 的大小，数组 $b$ 的大小，限制的个数 $L$

第 2 行包括 $n$ 个正整数，代表数组 $a$

第 3 行包括 $m$ 个正整数，代表数组 $b$

接下来 $L$ 行，每一行包含两个整数 $x, y$，代表 $a[x]$ 和 $b[y]$ 不能同时选中

输出格式

输出 1 行，包含 1 个正整数，代表满足条件的最大和，数据保证有解。

2 3 3
2 1
10 30 20
1 2
2 1
2 3

31

2 1 0
1000000000 1
1000000000

2000000000

10 10 10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127
7017 46004 16086 62644 74928 57404 32168 45794 19493 71590
1 3
2 6
4 5
5 4
5 5
5 6
5 7
5 8
5 10
7 3

149076

提示

• 样例 1 中
• 总共有 6 中组合
• a[1] + b[1] = 21
• a[1] + b[2] = 32, 不能选
• a[1] + b[3] = 22
• a[2] + b[1] = 11, 不能选
• a[2] + b[2] = 31
• a[2] + b[3] = 21, 不能选
• 在可选的 3 中组合里，最大和是 a[2] + b[2] = 31

数据规模与限制

• $1 \le n, m\le 10^5$
• $0 \le L \le min(10^5, n*m-1)$
• $1 \le a[i], b[j] \le 10^9$
• $1 \le x[i] \le n$
• $1 \le y[i] \le m$
• 1s, 1024KiB for each test case.