Description

地图上有$N$个Portal，现在某一名Agent的任务是占领该地图上的$M$个Portal，这名Agent占领第$i$个Portal可以得到的分数为$A[i]$，除了直接占领，还有其他的$K$种加分方式，对于着$N$个Portal，在占领完第$X[i]$个Portal后占领第$Y[i]$个Portal可以获得$B[i]$的加分，加分可能会有重复。Agent希望他可以为团队争取更多的分数，所以请求作为大战参谋的你来帮助他。

Input Format

第一行是输入三个整数$N,M,K$ 第二行输入是$N$个数，第$i$个数代表$A[i]$的值。 下面$K$行每行有3个整数$X[i],Y[i],C[i]$，表示在占领完第$X[i]$个Portal后占领第$Y[i]$个Portal可以获得$B[i]$的加分

Output Format

输出仅一行一个整数，为该名Agent可以获得的最大分数值。

3 2 1
1 1 1
1 2 3

5

4 3 2
1 1 1 1
4 3 2
3 2 1

6

Hint

对于$20\%$的数据 $1 \leq M \leq N \leq 4,0 \leq A[i],B[i] \leq 10^3$

对于$40\%$的数据 $1 \leq M \leq N \leq 8,0 \leq A[i],B[i] \leq 10^5$

对于$60\%$的数据 $1 \leq M \leq N \leq 12,0 \leq A[i],B[i] \leq 10^7$

对于$100\%$的数据 $1 \leq M,X[i],Y[i] \leq N \leq 18,0 \leq K \leq N^2−N,0 \leq A[i],B[i] \leq 10^9$