Петя и граф
У Пети есть простой граф (т. е. граф без петель и кратных ребер), состоящий из $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$. Во втором тестовом примере оптимальный подграф – пустой.
Задача на Codeforces (контест 1082, задача G, © Codeforces.com)