← 返回题目列表

Codeforces · 1082/G

G. Petya 和 Graph

中文机器翻译题面 查看原题

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$$$。在第二个测试用例中,最优子图为空。