题目描述

有$n$盘菜，每盘菜都有一个美味值。但是你只能选$m$盘菜。并且这些吃菜的顺序能影响总美味值。

如果$i$当且仅当在$j$之前吃(即吃$j$的前一个吃了$i$)，那么会额外加一些美味值，这样的组合有$k$组。

求选$m$盘菜吃能获得的最大的美味值。

输入格式

第一行为$n,m,k$ 第二行$n$个整数$a_i$($0 \leq a_i \leq 10^9$)代表每盘菜的美味值

接下来$k$行每行三个整数$x_i,y_i,c_i$($1 \leq x_i,y_i \leq n,x_i!=y_i,0 \leq c_i \leq 10^9$),代表在吃第$y_i$盘菜前吃第$x_i$盘菜会增加第$y_i$盘菜$c_i$的美味值，保证不会有相同的二元组($x_i,y_i$)。

输出格式

一个整数输出最大的美味值

样例

样例输入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

数据范围与提示

• 对于$50\\%$的数据，$1 \leq n \leq 10$
• 对于$100\\%$的数据,$1 \leq n,m \leq 15；k \leq 200$

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131022\mathrm{KB}$