"Почему, мастер," сказал Маленький Джон, беря мешки и взвешивая их в руке, "вот блеск золота."
Народный герой Робин Гуд сильно беспокоит шерифа Ноттингема. Шериф знает, что Робин Гуд собирается атаковать его лагеря, и он хочет быть готовым.
Шериф Ноттингема построил лагеря с учетом стратегии, и поэтому есть ровно \(n\) лагерей, пронумерованных от \(1\) до \(n\), и \(n-1\) троп, каждая из которых соединяет два лагеря. Любой лагерь можно достичь из любого другого лагеря. Каждый лагерь \(i\) изначально имеет \(a_i\) золота.
Шериф может укрепить лагерь, вычитая ровно \(c\) золота из каждого из его соседних лагерей и использовать это для строительства лучших защит для этого лагеря. Укрепление лагеря не изменяет его золото, только золото его соседей. Лагерь может иметь отрицательное количество золота.
После атаки Робина Гуда все лагеря, которые не были укреплены, будут уничтожены.
Какое максимальное количество золота шериф может сохранить в своих лагерях после атаки Робина Гуда, если он оптимально укрепляет свои лагеря?
Лагерь \(a\) является соседним лагерем \(b\), если и только если существует тропа, соединяющая \(a\) и \(b\). Только укрепленные лагеря учитываются в ответе, так как остальные будут уничтожены.
Выходные данные
Выведите одно целое число, максимальное золото, которое шериф Ноттингема может сохранить в своих выживших лагерях после атаки Робина Гуда.
Примечание
В первом наборе входных данных оптимально укрепить второй лагерь. Конечное золото в каждом лагере составляет \([1,3,0]\).
Во втором наборе входных данных оптимально укрепить все лагеря. Конечное золото в каждом лагере составляет \([2,4,2]\).
В третьем наборе входных данных оптимально не укреплять ни один лагерь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 1
2 3 1
1 2
2 3
3 1
3 6 3
1 2
2 3
3 1
-2 -3 -1
1 2
2 3
6 1
5 -4 3 6 7 3
4 1
5 1
3 5
3 6
1 2
8 1
3 5 2 7 8 5 -3 -4
7 3
1 8
4 3
3 5
7 6
8 7
2 1
|
3
8
0
17
26
|