套餐

题目描述

AtCoder 食堂出售由一份主菜和一份配菜组成的套餐。

共有 $N$ 种主菜,称为主菜 $1$、主菜 $2$、$\dots$、主菜 $N$。主菜 $i$ 的价格为 $a_i$ 日元。

共有 $M$ 种配菜,称为配菜 $1$、配菜 $2$、$\dots$、配菜 $M$。配菜 $i$ 的价格为 $b_i$ 日元。

套餐由选择一份主菜和一份配菜组成。套餐的价格为所选主菜与配菜的价格之和。

但是,对于 $L$ 个互不相同的数对 $(c_1, d_1), \dots, (c_L, d_L)$,由主菜 $c_i$ 和配菜 $d_i$ 组成的套餐因搭配不佳而不出售。

也就是说,共出售 $NM - L$ 种套餐。(数据范围保证至少出售一种套餐。)

求出售的套餐中最贵的套餐的价格。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $L$
$a_1$ $a_2$ $\dots$ $a_N$
$b_1$ $b_2$ $\dots$ $b_M$
$c_1$ $d_1$
$c_2$ $d_2$
$\vdots$
$c_L$ $d_L$

输出格式

输出出售的套餐中最贵的套餐的价格(日元)。

样例

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

31

共出售以下三种套餐:

• 由主菜 $1$ 和配菜 $1$ 组成的套餐,价格为 $2 + 10 = 12$ 日元。
• 由主菜 $1$ 和配菜 $3$ 组成的套餐,价格为 $2 + 20 = 22$ 日元。
• 由主菜 $2$ 和配菜 $2$ 组成的套餐,价格为 $1 + 30 = 31$ 日元。

其中最贵的是第三种,因此输出 $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 \le N, M \le 10^5$
• $0 \le L \le \min(10^5, NM - 1)$
• $1 \le a_i, b_i \le 10^9$
• $1 \le c_i \le N$
• $1 \le d_i \le M$
• 当 $i \neq j$ 时,$(c_i, d_i) \neq (c_j, d_j)$
• 所有输入值均为整数