题目描述

汪老师来到餐厅坐下后，服务员立刻给他拿来了菜单。菜单上有 $n$ 道菜。汪老师知道他需要吃$m$ 道菜。但他不想重复点同一道菜，想尝试尽可能多的菜。

汪老师知道第 $i$ 道菜能带给他 $a_i$ 单位的满足感。但有些菜不搭配，有些菜搭配得很好。汪老师给自己制定了 $k$ 条吃饭规则，第 $i$ 条吃饭规则表述为：如果他在吃第 $x_i$ 道菜之前正好吃了第 $y_i$ 道菜（中间没有隔着其他菜），那么他的满足感会额外增加 $c_i$ 单位。

当然，汪老师希望在餐厅里获得尽可能大的满足感。帮助他完成这个艰巨的任务吧！

输入格式

输入的第一行包含三个用空格分隔的数字 $n$、$m$ 和 $k$（$1 \le m \le n \le 18$，$0 \le k \le n(n-1)$） —— 菜单上的菜品数量、汪老师需要吃饱的菜品数量和吃饭规则的数量。

第二行包含 $n$ 个用空格分隔的数字 $a_i$（$0 \le a_i \le 10^9$） —— 他从第 $i$ 道菜中获得的满足感。

接下来的 $k$ 行包含了规则。第 $i$ 条规则由三个数字 $x_i$、$y_i$ 和 $c_i$（$1 \le x_i, y_i \le n, 0 \le c_i \le 10^9$）描述。这意味着如果汪老师在吃第 $x_i$ 道菜之前吃了第 $y_i$ 道菜，那么汪老师的满足感会额外增加 $c_i$ 单位。

数据保证对于任意 $1 \le i \lt j \le k$，不会出现 $x_i = x_j$ 且 $y_i = y_j$ 的情况出现。

输出格式

输出一个整数，表示汪老师在餐厅里能获得的最大满足感。

样例

2 2 1
1 1
2 1 1

3

4 3 2
1 2 3 4
2 1 5
3 4 2

12

说明/提示

样例解释

在第一个示例中，最好先吃第二道菜，然后再吃第一道菜。这样我们每道菜都能获得一单位的满足感，再加上规则的一单位。

在第二个测试中，最佳的选择序列是4 2 1或2 1 4。在这两种情况下，我们吃的菜总共能获得7单位的满足感，而且如果我们满足了规则1，还能额外获得5单位的满足感。