题目描述

小爱需要从 $n$ 道菜中，选出 $m$ 道菜作为餐厅的菜单。已知第 $i$ 道菜的美味值为 $x_i$。还有 $p$ 种加分规则，第 $i$ 条规则包含三个参数 $a_i$ 、$b_i$ 和 $c_i$，表示在第 $a_i$ 道菜后，如果下一道菜是 $b_i$ 道，会有额外 $c_i$ 点美味值。

如何设计菜单，才能使美味值到达最大。

输入格式

输入第一行，两个正整数$n,m$ 输入第二行，$n$个正整数，$x_1,...,x_n$ 输入第三行，一个正整数，$p$ ​接下来$p$行，每行$3$个正整数，分别表示第$i$条建议的三个参数$a_i,b_i,c_i$

输出格式

输出一个正整数，表示所选菜单能获得的最大美味值。

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

16

样例解释 1

按第2道、第1道、第4道备选菜肴的顺序组成正式菜单 获得 2+5+3=10 点美味值，外加第2道后接第1道备选菜肴所带来的 6 点额外美味值 故最大美味值为 16

数据范围

• 对于 $50\%$ 数据，$1 \leq m \leq n \leq 8$；
• 对于 $100\%$ 数据，$1\leq m \leq n \leq 18$； $0\leq x_i,c_i \leq 10^9 ,1 \leq a_i,b_i \leq n$ ，$1\leq p \leq n \times (n-1)$ 。

数据保证没有两条菜品建议的$a_i$和$b_i$完全相同