Дано дерево с \(n\) вершинами, пронумерованными от \(1\) до \(n\). Для вершины с номером \(i\) известна её высота \(h_i\). Вы можете установить любое количество вышек в вершины, для каждой вышки вы можете выбрать, в какую вершину её поставить, а также выбрать её эффективность. Установка вышки с эффективностью \(e\) стоит \(e\) монет, где \(e > 0\).
Считается, что в вершине \(x\) ловит связь, если для какой-то пары вышек в вершинах \(u\) и \(v\) (\(u \neq v\), но может быть, что \(x = u\) или \(x = v\)) с эффективностями соответственно \(e_u\) и \(e_v\) выполняется, что \(\min(e_u, e_v) \geq h_x\) и \(x\) лежит на пути между \(u\) и \(v\).
Найдите минимальное количество монет, необходимое для установки вышек, чтобы во всех вершинах ловила связь.
Выходные данные
Выведите одно целое число — минимальное необходимое количество монет, чтобы во всех вершинах ловила связь.
Примечание
В первом тесте оптимально установить две вышки с эффективностью \(2\) в \(1\) и \(3\) вершины.
Во втором тесте оптимально установить вышку с эффективностью \(1\) в вершину \(1\) и две вышки с эффективностью \(3\) во \(2\) и \(5\) вершины.
В третьем тесте оптимально установить две вышки с эффективностью \(6\) в \(1\) и \(2\) вершины.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 1
1 2
2 3
|
4
|
|
2
|
5
1 3 3 1 3
1 3
5 4
4 3
2 3
|
7
|
|
3
|
2
6 1
1 2
|
12
|