AT_abc331_e [ABC331E] Set Meal

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$

请输出所有可提供套餐中，价格最高的套餐的价格。

## 限制条件 - $1 \leq N, M \leq 10^5$ - $0 \leq L \leq \min(10^5, NM - 1)$ - $1 \leq a_i, b_i \leq 10^9$ - $1 \leq c_i \leq N$ - $1 \leq d_j \leq M$ - 如果 $i \neq j$，则 $(c_i, d_i) \neq (c_j, d_j)$ - 输入的所有数均为整数 ## 样例解释 1 可提供的套餐及其价格如下，共有 $3$ 种： - 主菜 $1$ 和副菜 $1$ 组成的套餐，价格为 $2 + 10 = 12$ 日元。 - 主菜 $1$ 和副菜 $3$ 组成的套餐，价格为 $2 + 20 = 22$ 日元。 - 主菜 $2$ 和副菜 $2$ 组成的套餐，价格为 $1 + 30 = 31$ 日元。 其中价格最高的套餐是第 $3$ 个套餐。因此请输出 $31$。 由 ChatGPT 4.1 翻译