$\text{Ysgg}$ 来到了一家餐厅。菜单上一共有 $n$ 道不同的菜，第 $i$ 道菜本身可以带来 $a_i$ 点满意度。

$\text{Ysgg}$ 恰好要选择其中 $m$ 道菜，并按照某个顺序依次吃完。每道菜最多只能选择一次。

除了每道菜本身的满意度之外，菜单中还有 $k$ 条搭配规则。每条规则由三个整数 $x$、$y$ 和 $c$ 描述：如果 $\text{Ysgg}$ 吃完第 $x$ 道菜后，紧接着吃第 $y$ 道菜，那么还会额外获得 $c$ 点满意度。

注意，搭配规则是有方向的。例如，若存在从第 $x$ 道菜到第 $y$ 道菜的奖励，并不意味着从第 $y$ 道菜到第 $x$ 道菜也有相同奖励。

请你帮助 $\text{Ysgg}$ 选择恰好 $m$ 道不同的菜，并确定进食顺序，使最终获得的总满意度尽可能大。

输入

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le m \le n \le 18$，$0 \le k \le n(n-1)$），分别表示菜单中的菜品数量、需要选择的菜品数量以及搭配规则数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 10^9$），其中 $a_i$ 表示选择第 $i$ 道菜本身能够获得的满意度。

接下来 $k$ 行，每行包含三个整数 $x$、$y$ 和 $c$（$1 \le x,y \le n$，$x\ne y$，$0 \le c \le 10^9$），表示如果第 $x$ 道菜后紧接着吃第 $y$ 道菜，可以额外获得 $c$ 点满意度。

保证不存在两条规则具有完全相同的有序对 $(x,y)$。

输出

输出一个整数，表示 $\text{Ysgg}$ 能够获得的最大总满意度。

样例

Input1

2 2 1
1 1
2 1 1

Output1

3

Input2

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

Output2

12

说明

对于样例 $1$，可以先吃第 $2$ 道菜，再吃第 $1$ 道菜。两道菜本身共提供 $2$ 点满意度，同时满足规则 $2\to1$，额外获得 $1$ 点满意度，因此总满意度为 $3$。

对于样例 $2$，一种最优顺序为 $4,2,1$。三道菜本身共提供 $4+2+1=7$ 点满意度，并满足规则 $2\to1$，额外获得 $5$ 点满意度，因此答案为 $12$。

数据范围

对于所有测试数据，满足：

• $1 \le m \le n \le 18$；
• $0 \le k \le n(n-1)$；
• $0 \le a_i \le 10^9$；
• $0 \le c \le 10^9$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

特殊性质：

• 性质 A：$k=0$；
• 性质 B：$m=1$；
• 性质 C：对于所有 $i$，均有 $a_i=0$；
• 性质 D：$a_1=a_2=\cdots=a_n$。

测试点编号	$n$	$m$	$k$	特殊性质
$1$	$\le 4$		$\le 12$	无
$2$	$\le 6$	$\le 5$	$\le 20$
$3\sim4$	$\le 10$	$\le 6$	$\le 40$
$5\sim6$	$\le 14$	$\le 8$	$\le 100$
$7$	$\le 18$	$1$	$\le n(n-1)$	B
$8$		$\le n$	$0$	A
$9$			$\le n(n-1)$	C
$10$				D
$11\sim12$	$\le 16$	$\le 12$	$\le 180$	无
$13\sim14$	$\le 17$	$\le 15$	$\le 240$
$15\sim20$	$\le 18$		$\le 306$