题目描述
小爱作为餐厅经理，他需要从 $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$
输出
输出一个正整数，表示所选菜单能获得的最大美味值。
样例输入输出
输入#1
复制
4 3
2 5 1 3
2
2 1 6
4 3 1
提示
+ 对于 $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$完全相同样
例1说明:按第2道、第1道、第4道备选菜肴的顺序组成正式菜单
获得 2+5+3=10 点美味值，外加第2道后接第1道备选菜肴所带来的 6 点额外美味值
故最大美味值为 16