Вы, убийца монстров, хотите убить группу монстров. Монстры находятся в дереве с \(n\) вершинами. В вершине с номером \(i\) (\(1\le i\le n\)) находится монстр с \(a_i\) очками атаки. Вы хотите сражаться с монстрами в течение \(10^{100}\) раундов.
В каждом раунде происходит следующее по порядку:
- Все живые монстры атакуют вас. Ваше здоровье уменьшается на сумму очков атаки всех живых монстров.
- Вы выбираете некоторых (возможно, всех или ни одного) монстров и убиваете их. После убийства монстр больше не сможет совершать атаки в будущем.
Также есть следующее ограничение: за один раунд вы не можете убить двух монстров, находящихся в соединенных ребром вершинах.
Если вы оптимально выбираете, каких монстров атаковать на каждом шагу, на какую минимальную величину может уменьшиться ваше здоровье за все раунды?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможное уменьшение здоровья.
Примечание
В первом наборе оптимальная последовательность операций следующая:
- В первом раунде: сначала получите атаку от монстра в вершине \(1\), поэтому ваше здоровье уменьшается на \(10^{12}\). Затем убейте монстра в вершине \(1\).
- Во втором раунде до \(10^{100}\)-го раунда: все монстры были убиты, поэтому ничего не происходит.
Общее уменьшение здоровья составляет \(10^{12}\).
Во втором наборе оптимальная последовательность операций следующая:
- В первом раунде: сначала получите атаку от монстров в вершинах \(1,2,3,4,5\), поэтому ваше здоровье уменьшается на \(47+15+32+29+23=146\). Затем убейте монстров в вершинах \(1,4,5\).
- Во втором раунде: сначала получите атаку от монстров в вершинах \(2,3\), поэтому ваше здоровье уменьшается на \(15+32=47\). Затем убейте монстров в вершинах \(2,3\).
- В третьем раунде до \(10^{100}\)-го раунда: все монстры были убиты, поэтому ничего не происходит.
Общее уменьшение здоровья составляет \(193\).
В третьем наборе оптимальная последовательность операций следующая:
- В первом раунде: сначала получите атаку от монстров в вершинах \(1,2,3,4,5,6,7\), поэтому ваше здоровье уменьшается на \(8+10+2+3+5+7+4=39\). Затем убейте монстров в вершинах \(1,3,6,7\).
- Во втором раунде: сначала получите атаку от монстров на вершинах \(2,4,5\), поэтому ваше здоровье уменьшается на \(10+3+5=18\). Затем убейте монстров на вершинах \(2,4,5\).
- В третьем раунде до \(10^{100}\)-го раунда: все монстры были убиты, поэтому ничего не происходит.
Общее уменьшение здоровья составляет \(57\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
1000000000000
5
47 15 32 29 23
1 2
1 3
2 4
2 5
7
8 10 2 3 5 7 4
1 2
1 4
3 2
5 3
6 2
7 5
|
1000000000000
193
57
|