Equal leaf distances

You are given a perfect binary tree of height $k$ whose edges carry positive weights. A perfect binary tree of height $k$ has $2^k$ leaves and $2^{k+1}-1$ nodes in total. The distance from the root to a leaf is the sum of the weights of every edge on the path between them.

In this problem you increase the weights of some edges so that the distance from the root to every leaf is the same, and you make the sum of all edge weights as small as possible. A weight can only be increased, never decreased.

For example, look at the perfect binary tree of height 2 in figure 1(a). The number written next to an edge is the weight of that edge. The answer for this tree is shown in figure 1(b). Every leaf sits at distance 5 from the root, and the sum of the edge weights is 15, the smallest value possible in this case.

Figure 1. An example of increasing edge weights.

Given every edge weight of a perfect binary tree, write a program that makes the distance from the root to every leaf equal while keeping the sum of the edge weights minimal.

Input is given on standard input. The first line contains a positive integer $k$, the height of the perfect binary tree. ($1 \le k \le 20$)

The second line contains the weights of all edges. The edges are listed starting from the level closest to the root, and within one level from left to right. There are $2^{k+1}-2$ edges, and each weight is an integer between 1 and 1,000.

Output uses standard output. Print on one line the sum of all edge weights of the tree obtained after the increases. Note that the weight of an edge may grow past 1,000.