포화이진트리 거리 맞추기

각 에지에 양수인 가중치가 붙은, 높이가 $k$인 포화이진트리가 주어진다. 높이가 $k$인 포화이진트리는 리프가 $2^k$개이고 노드가 모두 $2^{k+1}-1$개다. 루트에서 어떤 리프까지의 거리는 그 경로에 놓인 모든 에지의 가중치를 더한 값이다.

이 문제에서는 몇몇 에지의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리를 같게 만들려고 한다. 동시에 에지 가중치의 총합을 최소로 만들어야 한다. 가중치는 늘릴 수만 있고 줄일 수는 없다.

예를 들어 그림 1(a)의 높이 2인 포화이진트리를 보자. 에지 옆에 적힌 수가 그 에지의 가중치다. 이 트리에 대한 답이 그림 1(b)에 있다. 루트에서 모든 리프까지의 거리가 5이고, 에지 가중치의 총합은 이 경우에 가능한 최솟값인 15다.

그림 1. 에지 가중치를 증가시키는 예.

포화이진트리의 모든 에지 가중치가 주어졌을 때, 루트에서 모든 리프까지의 거리를 같게 만들면서 에지 가중치의 총합을 최소로 하는 프로그램을 작성하시오.

입력은 표준 입력으로 주어진다. 첫째 줄에 포화이진트리의 높이를 나타내는 양의 정수 $k$가 주어진다. ($1 \le k \le 20$)

둘째 줄에 모든 에지의 가중치가 주어진다. 에지는 루트에 가까운 레벨부터, 같은 레벨에서는 왼쪽에서 오른쪽 순서로 나열된다. 에지는 모두 $2^{k+1}-2$개이고, 각 가중치는 1 이상 1,000 이하인 정수다.

출력은 표준 출력을 사용한다. 가중치를 증가시킨 다음에 얻어지는 트리에서 모든 에지 가중치의 총합을 한 줄에 출력한다. 어떤 에지의 가중치는 경우에 따라 1,000보다 큰 값으로 증가할 수도 있으니 주의한다.