P4941 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,B_i$，表示在占领完第 $X_i$ 个 `Portal` 后**立即占领**第 $Y_i$ 个 `Portal` 可以获得 $B_i$ 的加分。

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

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