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 翻译