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$

输出格式

打印所提供的套餐中价格最高的一种的价格（日元）。

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 \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$ $(c_i, d_i) \neq (c_j, d_j)$ if $i \neq j$. 所有输入值均为整数。他们提供了三种套餐，列在下方，以及它们的价格：

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

其中最贵的是第三种。因此，输出 $31$。

标签: AtCoder|abc331E

来源

AtCoder|abc331E