劳动节要参与劳动，nodgd正在建筑工地上劳动。

仓库中有 \(A\) 种砖头和 \(B\) 种水泥。把砖头或者水泥从仓库搬运到工地，都会让身上变得很脏。搬运第 \(i(1\leq i\leq A)\) 种砖头会在衣服上积累 \(a_i\) 克的灰尘，搬运第 \(j(1\leq j\leq B)\) 种水泥会在衣服上积累 \(b_j\) 克的灰尘。

另外，使用特定的打包方式将砖头和水泥一起搬运，衣服上沾染的灰尘会单独搬运的灰尘总量少一些。这样的打包方式有 \(M\) 种：如果打包搬运第 \(x_i\) 种砖头和第 \(y_i\) 种水泥，衣服上沾染的灰尘会比单独搬运时减少 \(c_i\) 克。但是，不能同时使用多种打包方式。

nodgd的任务是将一种砖头和一种水泥从仓库搬运到工地，想知道最少沾染多少灰尘。

第一行3个整数 \(A,B,M\)；
第二行 \(A\) 个整数 \(a_1,\dots,a_A\)；
第三行 \(B\) 个整数 \(b_1,\dots,b_B\)；
第四行起的接下来 \(M\) 行，每行三个整数 \(x_i,y_i,c_i\)。

输出一个整数答案。

样例数据

输入输出样例1

样例输入
2 3 1
3 3
3 3 3
1 2 1

样例输出
5

打包搬运第 $1$ 种砖头和第 $2$ 种水泥，沾染灰尘 \(=3+3-1=5\) 克。

输入输出样例2

样例输入
1 1 2
10
10
1 1 5
1 1 10

样例输出
10

不能同时选择多种打包方式，所有沾染灰尘 \(=10+10-10=10\) 克。

输入输出样例3

样例输入
2 2 1
3 5
3 5
2 2 2

样例输出
6

分别搬运第 $1$ 种砖头和第 $1$ 种水泥。

数据规模与约定

输入的所有数据都是整数
$1\leq A,B,M, a_i,b_i,c_i\leq 10^5$
$1\leq x_i\leq A$
$1\leq y_i\leq B$
\(c_i\leq a_{x_i}+b_{y_i}\)