← 返回题目列表

AtCoder · hitachi2020_b

B. 愉快的购物

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

分数: 200 点

问题陈述

您正在一家大型电子商店购买冰箱和微波炉。

本店有售 A 各种冰箱和 B 种微波炉。 i第冰箱( 1 \le i \le A )售价为 a_i 日元(日本的货币),以及 j-th 微波 ( 1 \le j \le B )售价为 b_j 日元。

你有 M 折扣票。随着 i第一张票 ( 1 \le i \le M ),您可以获得以下折扣 c_i 日元购买时的总价 x_i第冰箱和 y_i一起微波。一次只能使用一张票。

您计划购买一台冰箱和一台微波炉。找出所需的最低金额。

约束

  • 输入中的所有值都是整数。
  • 1 \le A \le 10^5
  • 1 \le B \le 10^5
  • 1 \le M \le 10^5
  • 1 \le a_i , b_i , c_i \le 10^5
  • 1 \le x_i \le A
  • 1 \le y_i \le B
  • c_i \le a_{x_i} + b_{y_i}

输入

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

A B M
a_1 a_2 ... a_A
b_1 b_2 ... b_B
x_1 y_1 c_1
\vdots
x_M y_M c_M

输出

打印答案。


样本输入 1

2 3 1
3 3
3 3 3
1 2 1

示例输出 1

5

凭票即可获得 1-st 冰箱和 2-nd 微波炉 3+3-1=5 日元。


示例输入 2

1 1 2
10
10
1 1 5
1 1 10

示例输出 2

10

请注意,您一次不能使用多于一张门票。


示例输入 3

2 2 1
3 5
3 5
2 2 2

示例输出 3

6

您可以获得 1-st 冰箱和 1-st 微波炉 6 日元,这是这种情况下支付的最低金额。 请注意,是否使用门票是可选的。