配点 : $200$ 点

問題文

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

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

制約

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

出力

答えを出力せよ。

2 3 1
3 3
3 3 3
1 2 1

5

$1$ 番目の冷蔵庫と $2$ 番目の電子レンジを買うと、割引券の効果により $3+3-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$ 番目の冷蔵庫と $1$ 番目の電子レンジを買うと $6$ 円になり、これが最小です。 割引券は使わなくてもよいことに注意してください。