Ам Ням — главный герой игры Cut the Rope. Он — смышлёный маленький монстрик, который любит ходить в гости к друзьям, живущим по другую сторону парка. Однако старые тёмные парки могут напугать даже такое жизнерадостное существо как Ам Ням, поэтому он хочет обратиться к вам за помощью.

Парк представляет собой 2^n + 1 - 1 площадок, соединённых между собой дорожками так, что схема парка представляет собой полное бинарное дерево глубины n. Более формально, вход в парк ведёт в площадку 1. Выходы из парка расположены на площадках 2ⁿ, 2ⁿ + 1, ..., 2^n + 1 - 1, и эти выходы ведут прямо к домам друзей Ам Няма. От каждой площадки i (2 ≤ i < 2^n + 1) отходит двусторонняя дорожка в площадку . Таким образом, от входа в парк можно добраться до любого из выходов, пройдя ровно по n дорожкам.

Чтобы осветить дорожки парка вечером, смотритель парка установил фонари вдоль каждой дорожки. Вдоль дорожки, ведущей из i и в поставлено a_i фонарей.

Ам Ням любит считать фонари по пути к своему другу. Ам Ням побаивается пауков, которые живут в парке, поэтому он не любит ходить по мало освещённым маршрутам. Он хочет, чтобы на пути к любому из его друзей суммарно находилось одинаковое количество фонарей, тогда он будет чувствовать себя в безопасности.

Он обратился к вам за помощью в установке дополнительных фонарей. Определите, какое минимальное количество фонарей нужно дополнительно поставить на дорожки парка так, чтобы на пути от входа в парк до любого выхода из парка было одинаковое количество фонарей. На каждую дорожку можно добавить произовольное количество фонарей.