分数: 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 日元,这是这种情况下支付的最低金额。 请注意,是否使用门票是可选的。