A10007 | 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!

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}<=10^{9}$ ) — 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}<=10^{9}$ ). 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}$ .

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