War2

`XM大战`如期而至，`Agent`们齐聚一地，展开最后的对决。对战有很多种方式，有些复杂的方式可以获得更高的分数。可惜`ENLIGHTENED`的人并不怎么聪明，只会简单的`hack`，所以`ENLIGHTENED行动指挥`找到了你来做他们的总参谋。

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

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

输出仅一行一个整数，为该名`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

对于$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$