题目背景

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$