G. Петя и граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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