题目描述

Kefa 来到一家餐厅。菜单上有 $n$ 道菜，他恰好需要吃 $m$ 道，并且每道菜至多吃一次。

第 $i$ 道菜能带来 $a_i$ 点满意度。此外有 $k$ 条额外规则：若 Kefa 紧接着吃完第 $x$ 道菜后立刻吃第 $y$ 道菜，中间没有其他菜，则额外获得 $c$ 点满意度。

请你安排要吃的 $m$ 道菜及其顺序，使总满意度最大。

输入格式

第一行三个整数 $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$ 行，每行三个整数 $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$ 点满意度。

保证不会出现两条规则具有相同的有序对 $(x_i,y_i)$。

输出格式

输出一个整数，表示 Kefa 能得到的最大总满意度。

样例

输入 1

2 2 1
1 1
2 1 1

输出 1

3

输入 2

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

输出 2

12

样例说明

第一组中，先吃第 $2$ 道菜，再吃第 $1$ 道菜，可获得两道菜的基础满意度 $2$，以及规则带来的 $1$ 点额外满意度，总计 $3$。

第二组中，可选择顺序 $4,2,1$ 或 $2,1,4$。基础满意度为 $1+2+4=7$，再满足规则 $2\to1$ 得到 $5$ 点额外满意度，总计 $12$。