问题描述

你正在访问一家大型电子商店购买一台冰箱和一台微波炉。

该商店销售 $A$ 种冰箱和 $B$ 种微波炉。第 $i$ 台冰箱（$1 \le i \le A$）的售价为 $a_i$ 日元（日本的货币单位），第 $j$ 台微波炉（$1 \le j \le B$）的售价为 $b_j$ 日元。

你有 $M$ 张折扣券。使用第 $i$ 张券（$1 \le i \le M$），你可以在购买第 $x_i$ 台冰箱和第 $y_i$ 台微波炉时，从总价中获得 $c_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

凭借这张券，你可以用 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

在这种情况下，你可以以 6 日元的最低价格购买第一台冰箱和第一台微波炉。请注意，使用券是可选的。