一個維度為 n 的 hypercube 是由\(2^{n}\)個節點組成的網路，每個節點被賦予唯一一個\(0\)～\(2^{n}-1\)的編號，對於任兩個節點 i 與 j，他們之間會有邊相連若且惟若 i 與 j 的二進位編碼恰好相差一個位元，我們對於每個節點 i 給予一個正整數的權重 w(i)， 請找出編號 \(0\) 到編號\(2^{n}-1\)的一條最短路徑，使得該路徑所經過的點權重總合(包含起點與終點)為最大。

輸入格式

第一行是正整數 n， 第二行則是這\(2^{n}\)個節點的正整數權重 w(0),w(1),…,w(\(2^{n}-1\))數字之間以一個空白間隔， 其中 n<20 而每個權重值為非負整數不超過 100。

輸出格式

最大權重總和。

範例輸入 1

2
1 2 3 4

範例輸出 1

8

範例輸入 2

3
1 2 3 4 5 6 7 8

範例輸出 2

21