该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

$panda$准备为比赛购买一些奖品，为此他来到了一家商店。

这家商店出售 $A$ 类奖品和 $B$ 类奖品。第 $i$ 种奖品 ($1 \le i \le A$) 以 a_i元出售，第 $j$ 种奖品 ($1 \le j \le B$)售价为 $b_j$元。

$panda$有 $M$ 张优惠票。使用第 $i$ 张票 ($1 \le i \le M$)，当一起购买第 $x_i$ 个 $A$ 类奖品和第 $y_i$ 个 $B$ 类奖品时，可以从总价格中获得 $c_i$ 元的折扣。一次只能使用一张票。

$panda$现在打算购买一种 $A$ 类产品和一种 $B$ 类产品。他需要找到所需的最低金额。

Input Format

你将会从prize.in中读入数据。

你会获得以下输入：

$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$

Output Format

你的结果需要输出到prize.out中，输出最低金额。

Sample

Sample Input 1

2 3 1
3 3
3 3 3
1 2 1

Sample Output 1

5

Sample Input 2

2 2 1
3 5
3 5
2 2 2

Sample Output 2

6

Hint

• $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}$