← 返回题目列表

AtCoder · abc331_e

H. 套餐

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

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 套餐。 (限制条件保证至少提供一份套餐。)

查找提供的最贵套餐的价格。

约束

  • 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.
  • 所有输入值均为整数。

输入

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

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

他们提供三份套餐,如下所列,及其价格:

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

其中最贵的是第三个。因此,打印 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

149076