AT_hitachi2020_b.Nice Shopping

你来到一家家电量贩店，打算购买冰箱和微波炉。

这家家电量贩店出售 $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$ 日元。注意，不能同时使用多张优惠券。

你打算恰好购买一台冰箱和一台微波炉。请你求出所需支付金额的最小值。

输入按以下格式从标准输入给出。

$A$ $B$ $M$
$a_1$ $a_2$ $\ldots$ $a_A$
$b_1$ $b_2$ $\ldots$ $b_B$
$x_1$ $y_1$ $c_1$
$\vdots$
$x_M$ $y_M$ $c_M$

请输出答案。

限制条件

• 所有输入均为整数。
• $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}$

样例解释 1

如果购买第 $1$ 种冰箱和第 $2$ 种微波炉，使用优惠券后，支付金额为 $3+3-1=5$ 日元。

样例解释 2

请注意，不能同时使用多张优惠券。

样例解释 3

在这种情况下，购买第 $1$ 种冰箱和第 $1$ 种微波炉的总价为 $6$ 日元，这是最小值。注意，即使不使用优惠券也是可以的。

由 ChatGPT 4.1 翻译