В ряд лежать \(N\) крапель. Кожна крапля маєм масу \(Ai\).
За один хід можна об'єднати дві сусідні краплі. Якщо маси цих крапель були \(x\) та \(y\) то на їх місці утвориться нова крапля, масою \(x+y\) і на це буде витрачено \(x+y\) енергії. В подальшому цю краплю теж можна об'єднувати з сусідами.

Знайдіть мінімальну кількість енергії, яка необхідна, для об'єднання усіх крапель в одну.

Формат вхідних даних

Перший рядок містить число число \(N\) - кількість блоків (\(1 \le N \le 400\)).
Наступний рядок містить \(N\) цілих чисел \(Ai\) (\(1 \le Ai \le 10^9\))

Формат вихідних даних

Виведіть єдине число - мінімальну кількість енергії, якої достатньо для об'єднання усіх крапель.

Приклад вхідних даних-1

4
10 20 30 40

Приклад вихідних даних-1

190

Приклад вхідних даних-2

5
10 10 10 10 10

Приклад вихідних даних-2

120

Приклад вхідних даних-3

6
7 6 8 6 1 1

Приклад вихідних даних-3

68