### 问题描述 未来学校新一届运动会就要来了，信息学 $1$ 班高度重视这次大赛，为了备战接力赛，决定从 $n$ 位预备选手中选出 $m$ 位组成正式队伍来参加比赛。这些预备选手都有一个基本的水平评分，当他们组成正式队伍后，教练需要决定他们的出场顺序，而某些选手之间可能彼此之间配合非常默契，这样能大大降低接棒失误的概率，额外提高队伍的评分。 假如你是信息学 $1$ 班的教练，请你选出最强的 $m$ 位选手，确认他们的出战顺序，使得他们组成的正式队伍评分最高。 ### 输入格式 第一行输入三个正整数 $n，m，k。n$ 为预备选手人数， $m$ 为参赛选手人数， $k$ 表示这些同学之间有k种特殊关系。 第二行包含 $n$ 个整数 $a_i$ ，表示每位预备选手的实力评分。 接下来有 $k$ 行，每行包含三个整数 $x_i,y_i,c_i$ ，表示这种特殊关系：即如果在出战顺序中， $y_i$ 这名同学紧挨在 $x_i$ 同学之后，他们之间就会产生默契，从而额外提高队伍 $c_i$ 的评分。 保证输入数据不会出现重复的特殊关系，也不会有 $x_i=y_i$ 。 ### 输出格式 输出一行一个整数，为正式参赛队伍的最大实力评分。 ### 样例输入1 ```plaintext 2 2 1 1 1 2 1 1 ``` ### 样例输出1 ```plaintext 3 ``` ### 样例输入2 ```plaintext 4 3 2 1 2 3 4 2 1 5 3 4 2 ``` ### 样例输出2 ```plaintext 12 ``` ### 数据范围 对于 $30\\%$ 的数据， $k=0$ 。 对于 $100\\%$ 的数据， $1 \le m \le n \le 18 , 0 \le k \le n \times (n-1) , 1 \le a_i \le 10^9 , 1 \le x_i ,y_i \le n , 0 \le c_i \le 10^9$ 。