Задано корневое дерево, состоящее из \(n\) вершин. Вершины в дереве пронумерованы от \(1\) до \(n\), вершина \(1\) — корень. Значение \(a_i\) записано в \(i\)-й вершине.
Вы можете выполнять следующую операцию любое количество раз (возможно, ноль): выбрать вершину \(v\), у которой есть хотя бы один сын; увеличить \(a_v\) на \(1\); и уменьшить \(a_u\) на \(1\) для всех вершин \(u\), которые находятся в поддереве \(v\) (за исключением самой \(v\)). Но после каждой операции значения на всех вершинах должны быть неотрицательными.
Ваша задача — посчитать максимальное возможное значение в корне, используя вышеописанную операцию.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное возможное значение в корне, используя вышеописанную операцию.
Примечание
В первом наборе входных данных возможна следующая последовательность операций:
- провести операцию на \(v=3\), тогда значения на вершинах станут \([0, 1, 1, 1]\);
- провести операцию на \(v=1\), тогда значения на вершинах станут \([1, 0, 0, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2
|
1
3
6
|