分数: 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