配点 : $1000$ 点

問題文

非負整数のひとつ書かれたカードが $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$ 枚のカードに書かれた整数の和の最小値を出力せよ。

4
3 1 4 2

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$ になる。

6
5 2 4 1 6 9

51

10
3 1 4 1 5 9 2 6 5 3

115