题目描述

王老师的炸弹淘汰计划由于教导处的介入以失败告终，他只好回到班上淘汰自己的学生。
王老师班上有 n 个学生。在回来之前王老师就想好了要淘汰 m 个学生，这样他的班才跑得起来。
王老师为每个学生设定了一个淘汰值为 ai，每淘汰一个学生，王老师的满意度增加 ai。但是有些学生淘汰起来很舒服，而有些学生淘汰着就不怎么爽。如果选择淘汰的顺序不同可能会得到不同的满意度。对此王老师列了 k 条规则，对于学生 xi 和 yi，如果先淘汰 xi 再淘汰 yi（xi 和 yi 之间没有其他学生），王老师的满意度会在原基础上额外增加 ci（既 w = axi + ayi + ci）。王老师想知道如何选择学生以及淘汰的顺序才能使他的满意度最大。

输入格式

第一行输入三个整数 n, m, k。
第二行输入 n 个学生的淘汰值 ai。
第三行输入 k 个规则，xi, yi, ci。

输出格式

输出王老师能够得到的最大满意度。

样例1

输入

2 2 1
1 1
2 1 1

输出

3

样例2

输入

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

输出

12

数据范围

对于 30%的数据，1 <= m <= n <= 10。
对于 100%的数据，1 <= m <= n <= 18，0 <= k <= n * (n - 1)，0 <= ai <= 10^9。

限制

1s

样例解释

样例 2：选择学生 1, 2, 4，淘汰的顺序为 2 -> 1 -> 4，满意度 w = 2 + 1 + 5 + 4 = 12。

来源

Codeforces580D
CWOI新高二专题测试五