Petya 有一个简单的图(即没有循环或多条边的图),由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。
第 $$$i$$$ 个顶点的权重为 $$$a_i$$$。
第 $$$i$$$ 条边的权重为 $$$w_i$$$。
图的子图是图顶点的某些集合和图边的某些集合。边集必须满足条件:该集中每条边的两端必须属于所选顶点集。
子图的权重是其边的权重之和减去其顶点的权重之和。您需要找到给定图的子图的最大权重。给定的图不包含循环和多重边。
输入
第一行包含两个数字 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^3, 0 \le m \le 10^3$$$) - 分别是图中的顶点和边的数量。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 图顶点的权重。
以下 $$$m$$$ 行包含边:$$$i$$$-e 边由整数三元组 $$$v_i, u_i, w_i$$$ ($$$1 \le v_i, u_i \le n, 1 \le w_i \le 10^9, v_i \neq u_i$$$) 定义。这个三元组意味着在顶点 $$$v_i$$$ 和 $$$u_i$$$ 之间有一条权重为 $$$w_i$$$ 的边。保证图不包含环和重边。
输出
打印一个整数 — 给定图的子图的最大权重。
示例
输入 #1
4 5 1 5 2 2 1 3 4 1 4 4 3 4 5 3 2 2 4 2 2
输出 #1
8
输入 #2
3 3 9 7 8 1 2 1 2 3 2 1 3 3
输出 #2
0
注意
在第一个测试示例中,最优子图由顶点 $$${1, 3, 4}$$$ 组成,权重为 $$$4 + 4 + 5 - (1 + 2 + 2) = 8$$$。在第二个测试用例中,最优子图为空。