Om Nom and Dark Park

题意翻译

一个有着2^(n+1)满二叉树，每条边都有权值，你可以为每条边增加任意的权值，使得从根节点到每一个叶子节点的路径上的权值之和相等，要求增加权值的总和在满足条件的情况下尽量小 输入： 第一行 n 第二行，2^(n+1)-2个数，第i个数表示i+1号节点与其父亲节点的边的权值（这里的点的编号指的是按层次标号） 输出： 一行一个整数，表示在保证根到每一个叶子节点的路径权值和相等的情况下，增加权值的最小值 数据范围： n≤10

题目描述

Om Nom is the main character of a game "Cut the Rope". He is a bright little monster who likes visiting friends living at the other side of the park. However the dark old parks can scare even somebody as fearless as Om Nom, so he asks you to help him. The park consists of $ 2^{n+1}-1 $ squares connected by roads so that the scheme of the park is a full binary tree of depth $ n $ . More formally, the entrance to the park is located at the square $ 1 $ . The exits out of the park are located at squares $ 2^{n},2^{n}+1,...,2^{n+1}-1 $ and these exits lead straight to the Om Nom friends' houses. From each square $ i $ ( $ 2<=i<2^{n+1} $ ) there is a road to the square . Thus, it is possible to go from the park entrance to each of the exits by walking along exactly $ n $ roads.  To light the path roads in the evening, the park keeper installed street lights along each road. The road that leads from square $ i $ to square  has $ a_{i} $ lights.Om Nom loves counting lights on the way to his friend. Om Nom is afraid of spiders who live in the park, so he doesn't like to walk along roads that are not enough lit. What he wants is that the way to any of his friends should have in total the same number of lights. That will make him feel safe. He asked you to help him install additional lights. Determine what minimum number of lights it is needed to additionally place on the park roads so that a path from the entrance to any exit of the park contains the same number of street lights. You may add an arbitrary number of street lights to each of the roads.

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=10 $ ) — the number of roads on the path from the entrance to any exit. The next line contains $ 2^{n+1}-2 $ numbers $ a_{2},a_{3},...\ a_{2^{n+1}-1} $ — the initial numbers of street lights on each road of the park. Here $ a_{i} $ is the number of street lights on the road between squares $ i $ and . All numbers $ a_{i} $ are positive integers, not exceeding $ 100 $ .

输出格式

Print the minimum number of street lights that we should add to the roads of the park to make Om Nom feel safe.

输入输出样例

输入样例 #1

2
1 2 3 4 5 6

输出样例 #1

5

说明

Picture for the sample test. Green color denotes the additional street lights.