Дано корневое дерево, состоящее из n вершин. В каждом листе дерева записано ровно одно число — количество яблок в этом листе.
Весом поддерева назовем сумму чисел в листьях этого поддерева. В частности, вес поддерева, соответствующего некоторому листу — это число, которое записано в этом листе.
Дерево называется сбалансированным, если для каждой вершины дерева v все поддеревья, соответствующие сыновьям вершины v, имеют одинаковый вес.
Какое минимальное количество яблок нужно удалить из дерева (точнее из некоторых его листьев), чтобы сделать дерево сбалансированным? Обратите внимание, что цель всегда можно достигнуть, удалив все яблоки.
Выходные данные
Выведите единственное целое число — минимальное количество яблок, которое нужно удалить, чтобы сбалансировать дерево.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
0 0 12 13 5 6
1 2
1 3
1 4
2 5
2 6
|
6
|