E : Sigma / Σ

Problem

小学生のづあい君は同じ足し算にも得意不得意があり、 0 以上の整数 X, Y に対して、X + Y を計算するのにかかる時間(秒)が次のように決まる。

• 1 の位から順番に計算していく。
• 10 進数表記で 10ⁱ 位の計算には x_i × y_i + c_i 秒かかる。
  • x_i は X の10進数表記で 10ⁱ の位の数である。
  • y_i は Y の10進数表記で 10ⁱ の位の数である。
  • ただし i が X の桁数より大きくなる時は x_i = 0 とする。Y についても同様である。
  • c_i は、 i = 0 または x_i-1 + y_i-1 + c_i-1 < 10 ならば 0、 そうでなければ 1 である。
• 0 以上の整数 i についての x_i × y_i + c_i の総和が X + Y の計算にかかる時間である。

ある日、づあい君の先生は長さ N の整数列 a₀, ... , a_N-1 の和を計算する宿題を出した。づあい君は数列の順番を並び替えることはできないが、足し算の式に括弧を付けることにより、足し算の順番を自由に変えることができる。例えば N = 4 の場合、順番は次の 5 通りある。

• ((a₀ + a₁) + a₂) + a₃
• (a₀ + a₁) + (a₂ + a₃)
• (a₀ + (a₁ + a₂)) + a₃
• a₀ + ((a₁ + a₂) + a₃)
• a₀ + (a₁ + (a₂ + a₃))

それぞれの括弧 (x + y) の中で上で説明した時間がかかるとすると、総和を求めるのにかかる時間は最小で何秒になるだろうか。

Input

入力は次のような形式で与えられる。

N
a₀ a₁ ... a_N-1

Constraints

• 入力はすべて整数である。
• 2 ≦ N ≦ 300
• 0 ≦ a_i ≦ 1,000,000

Output

答えの秒数を1行で出力せよ。

Samples

Sample Input 1

3
1 2 3

Sample Output 1

11

次のように計算すると最も速い。

• 2 + 3 = 5 ( 2 × 3 = 6 秒かかる)
• 1 + 5 = 6 ( 1 × 5 = 5 秒かかる)