Sigma

Time Limit : 1 sec, Memory Limit : 131072 KB

E : Sigma / Σ

Problem

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

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

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

  • ((a0 + a1) + a2) + a3
  • (a0 + a1) + (a2 + a3)
  • (a0 + (a1 + a2)) + a3
  • a0 + ((a1 + a2) + a3)
  • a0 + (a1 + (a2 + a3))

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

Input

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

N
a0 a1 ... aN-1

Constraints

  • 入力はすべて整数である。
  • 2 ≦ N ≦ 300
  • 0 ≦ ai ≦ 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 秒かかる)

Source: Aizu Competitive Programming Camp 2014 Day3 , Japan, 2014-09-25