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

输入 #1

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

输出 #1

31

输入输出样例 #2

输入 #2

2 1 0
1000000000 1
1000000000

输出 #2

2000000000

输入输出样例 #3

输入 #3

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

输出 #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$
• 如果 $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 翻译