CF580D.Kefa and Dishes

When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were n dishes. Kefa knows that he needs exactly m dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible.

Kefa knows that the i-th dish gives him a__i units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself k rules of eating food of the following type — if he eats dish x exactly before dish y (there should be no other dishes between x and y), then his satisfaction level raises by c.

Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task!

当基法来到餐厅并在一张桌子旁坐下时，服务员立即为他送上了菜单。菜单上有 $n$ 道菜。基法知道他恰好需要点 $m$ 道菜。此外，他不想重复点同一道菜，以尽可能多地品尝不同菜品。

基法知道第 $i$ 道菜能给他带来 $a_i$ 单位的满足感。但某些菜品之间搭配不佳，而另一些则非常相配。基法为自己设定了 $k$ 条用餐规则，形式如下：如果他恰好在菜品 $x$ 之后紧接着点菜品 $y$（即 $x$ 和 $y$ 之间不能有其他菜品），那么他的满足感将额外增加 $c$。

当然，这只鹦鹉希望从这次餐厅就餐中获得尽可能大的满足感！请帮他完成这项艰巨的任务！

The first line of the input contains three space-separated numbers, n, m and k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n * (n - 1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules.

The second line contains n space-separated numbers a__i, (0 ≤ a__i ≤ 109) — the satisfaction he gets from the i-th dish.

Next k lines contain the rules. The i-th rule is described by the three numbers x__i, y__i and c__i (1 ≤ x__i, y__i ≤ n, 0 ≤ c__i ≤ 109). That means that if you eat dish x__i right before dish y__i, then the Kefa's satisfaction increases by c__i. It is guaranteed that there are no such pairs of indexes i and j (1 ≤ i < j ≤ k), that x__i = x__j and y__i = y__j.

输入的第一行包含三个用空格分隔的整数 $n$、$m$ 和 $k$（$1 ≤ m ≤ n ≤ 18$，$0 ≤ k ≤ n × (n - 1)$）——分别表示菜单上的菜肴数量、Kefa 为吃饱所需食用的份数，以及进食规则的数量。

第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 ≤ a_i ≤ 10^9$）——表示 Kefa 从第 $i$ 道菜肴中获得的满足感。

接下来的 $k$ 行描述了这些规则。第 $i$ 条规则由三个整数 $x_i$、$y_i$ 和 $c_i$（$1 ≤ x_i,\,y_i ≤ n$，$0 ≤ c_i ≤ 10^9$）给出。其含义是：若你恰好在食用菜肴 $y_i$ 之前食用菜肴 $x_i$，则 Kefa 的满足感将额外增加 $c_i$。保证不存在下标对 $i$ 和 $j$（$1 ≤ i < j ≤ k$），使得 $x_i = x_j$ 且 $y_i = y_j$。

In the single line of the output print the maximum satisfaction that Kefa can get from going to the restaurant.

在输出的单行中打印基法去餐厅所能获得的最大满意度。

In the first sample it is best to first eat the second dish, then the first one. Then we get one unit of satisfaction for each dish and plus one more for the rule.

In the second test the fitting sequences of choice are 4 2 1 or 2 1 4. In both cases we get satisfaction 7 for dishes and also, if we fulfill rule 1, we get an additional satisfaction 5.

在第一个样例中，最优策略是先吃第二道菜，再吃第一道菜。这样每道菜各获得 1 单位满足度，并且由于满足了规则，额外再获得 1 单位满足度。

在第二个测试用例中，符合条件的选择序列有 $4\ 2\ 1$ 或 $2\ 1\ 4$。在这两种情况下，菜肴本身带来的满足度总和均为 7；此外，若满足规则 1，则还可额外获得 5 单位满足度。