У Пети есть простой граф (т. е. граф без петель и кратных ребер), состоящий из \(n\) вершин и \(m\) ребер.
Вес \(i\)-й вершины равен \(a_i\).
Вес \(i\)-го ребра равен \(w_i\).
Подграфом графа будем называть некоторое множество вершин графа и некоторое множество ребер графа, причем множество ребер должно удовлетворять условию: оба конца каждого ребра из множества должны принадлежать выбранному множеству вершин.
Весом подграфа является сумма весов входящих в него ребер минус сумма весов входящих в него вершин. Вам нужно найти подграф данного графа максимального веса. Заданный граф не содержит петель и кратных ребер.
Выходные данные
В единственной строке выведите целое число — максимальный вес подграфа заданного графа.
Примечание
В первом тестовом примере оптимальный подграф состоит из вершин \({1, 3, 4}\) и имеет вес \(4 + 4 + 5 - (1 + 2 + 2) = 8\). Во втором тестовом примере оптимальный подграф – пустой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 5 2 2
1 3 4
1 4 4
3 4 5
3 2 2
4 2 2
|
8
|
|
2
|
3 3
9 7 8
1 2 1
2 3 2
1 3 3
|
0
|