У Пети есть простой граф (т. е. граф без петель и кратных ребер), состоящий из $$$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$$$-е ребро задаётся тройкой целых чисел $$$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$$$. Гарантируется, что граф не содержит петель и кратных рёбер.
В единственной строке выведите целое число — максимальный вес подграфа заданного графа.
4 5 1 5 2 2 1 3 4 1 4 4 3 4 5 3 2 2 4 2 2
8
3 3 9 7 8 1 2 1 2 3 2 1 3 3
0
В первом тестовом примере оптимальный подграф состоит из вершин $$${1, 3, 4}$$$ и имеет вес $$$4 + 4 + 5 - (1 + 2 + 2) = 8$$$. Во втором тестовом примере оптимальный подграф – пустой.
Название |
---|