問題文

非負整数のひとつ書かれたカードが $N$ 枚積まれた山があります。上から $i$ 番目のカードに書かれた整数は $A_i$ です。

すぬけ君は、以下の操作をカードが $2$ 枚になるまで繰り返します。

• 連続して積まれている $3$ 枚のカードを選ぶ。
• $3$ 枚のうち真ん中のカードを食べる。
• あとの $2$ 枚のカードに書かれている整数を、その整数に食べたカードに書かれていた整数を足してできる整数に書き換える。
• 食べなかった $2$ 枚のカードを、順序を保ったまま山のもとの位置に戻す。

最終的に残る $2$ 枚のカードに書かれた整数の和の最小値を求めてください。

制約

• $2 \\leq N \\leq 18$
• $0 \\leq A_i \\leq 10^9 (1\\leq i\\leq N)$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $...$ $A_N$

出力

最終的に残る $2$ 枚のカードに書かれた整数の和の最小値を出力せよ。

入力例 1

4
3 1 4 2

出力例 1

16

以下の操作を行うことで、最終的に残る $2$ 枚のカードに書かれた整数の和を最小にできます。

• 最初、カードに書かれた整数は順に $3,1,4,2$ である。
• $1,2,3$ 番目のカードを選ぶ。$1$ の書かれた $2$ 枚目のカードを食べ、残ったカードに書かれた整数に $1$ を足し、山のもとの位置に戻す。カードに書かれた整数は順に $4,5,2$ となる。
• $1,2,3$ 番目のカードを選ぶ。$5$ の書かれた $2$ 枚目のカードを食べ、残ったカードに書かれた整数に $5$ を足し、山のもとの位置に戻す。カードに書かれた整数は順に $9,7$ となる。
• 最後に残った $2$ 枚のカードに書かれた整数の和は $16$ になる。

入力例 2

6
5 2 4 1 6 9

出力例 2

51

入力例 3

10
3 1 4 1 5 9 2 6 5 3

出力例 3

115