背景

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 可以获得的最大分数值。

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