AT_abc331_e.[ABC331E] Set Meal

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```
2 3 3
2 1
10 30 20
1 2
2 1
2 3
```
输出#1
```
31
```
输入#2
```
2 1 0
1000000000 1
1000000000
```
输出#2
```
2000000000
```

输入#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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页