У Мити есть корневое дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\), причем корень дерева имеет номер \(1\). В каждой его вершине \(v\) было записано целое число \(a_v \ge 0\). Для каждой вершины \(v\) Митя вычислил величину \(s_v\): сумму чисел, записанных на пути от вершины \(v\) до корня, а также \(h_v\) — глубину вершины \(v\), то есть количество вершин на пути от вершины \(v\) до корня (таким образом, \(s_1=a_1\), \(h_1=1\)).
После этого Митя уничтожил исходные значения \(a_v\). К сожалению, он также случайно уничтожил все значения \(s_v\) для вершин, находящихся на четной глубине (то есть тех, для которых \(h_v\) является четным). Ваша задача состоит в том, чтобы восстановить значения \(a_v\) для каждой из вершин либо определить, что это невозможно. Среди возможных вариантов нужно выбрать тот, при котором сумма значений \(a_v\) во всем дереве является минимально возможной.
Выходные данные
Выведите единственное число — минимально возможную сумму чисел \(a_v\) в вершинах исходного дерева или \(-1\), если такого дерева не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 1 1
1 -1 -1 -1 -1
|
1
|
|
2
|
5
1 2 3 1
1 -1 2 -1 -1
|
2
|
|
3
|
3
1 2
2 -1 1
|
-1
|