题目描述

あなたは、冷蔵庫と電子レンジを買うために、とある家電量販店に来ました。

この家電量販店では、 $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$ 台ずつ買おうと思っています。かかる金額の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

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

这家商店出售 $A$ 类冰箱和 $B$ 类微波炉。第 $i$ 台冰箱 $(1 \le i \le)$ 以 $a_i$ 日元出售，第 $j$ 个微波炉 $(1 \le j \le B)$ 售价为 $b_j$ 日元。

您有 $M$ 张优惠票。使用第 $i$ 张票 $(1 \le i \le M)$，当一起购买第 $x_i$ 个冰箱和第 $y_i$ 个微波炉时，您可以从总价格中获得 $c_i$ 日元的折扣。一次只能使用一张票。

您打算购买一台冰箱和一台微波炉。 找到所需的最低金额。

2 3 1
3 3
3 3 3
1 2 1

5

1 1 2
10
10
1 1 5
1 1 10

10

2 2 1
3 5
3 5
2 2 2

6

提示

制約

• 入力は全て整数
• $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}$

Sample Explanation 1

$1$ 番目の冷蔵庫と $2$ 番目の電子レンジを買うと、割引券の効果により $3+3-1=5$ 円になります。

Sample Explanation 2

複数の割引券を同時に使うことはできないことに注意してください。

Sample Explanation 3

この場合は $1$ 番目の冷蔵庫と $1$ 番目の電子レンジを買うと $6$ 円になり、これが最小です。 割引券は使わなくてもよいことに注意してください。