Мали Том је био неваљао, и за казну је добио задужење да офарба зид. Зид се може представити као матрица са \(N\) врста и \(M\) колона. Том има јако чудну четку којом може у \(i\)-тој врсти да офарба или првих \(A_i\) колона или последњих \(M-A_i\) колона. Тому је свака колона досадна онолико колико износи производ броја офарбаних и неофарбаних поља у тој колони. Укупна досадност зида је једнака збиру досадности свих колона. Помозите Тому и израчунајте најмању могућу досадност зида након бојења.

Опис улаза

У првој линији стандардног улаза се налазе два цела броја, \(N\) и \(M\), која представљају број врста и број колона, У наредних \(N\) линија се налази по један цео број, \(A_i\), који представља границу за фарбање \(i\)-те врсте (\(0 \leq A_i \leq M\)).

Опис излаза

У јединој линији стандардног излаза се налази један цео број који представља минималну досадност зида након фарбања.

Пример 1

Улаз

2 3
1
2

Излаз

1

Пример 2

Улаз

4 4
2 
1 
4 
1

Излаз

6

Објашњење примера

У првом примеру је најбоље офарбати обе врсте са десне стране и онда би укупна досадност била \(2 \cdot 0 + 1 \cdot 1 + 0 \cdot 2 = 1\). ~~~ .## ..# ~~~

У другом примеру је најбоље прву, другу и четврту врсту офарбати са леве стране, а трећу са десне (пошто је \(A_3 = M\) она ће онда остати неофарбана). ~~~ ##.. #… …. #… ~~~ Укупна досадност је \(1 \cdot 3 + 3 \cdot 1 + 4 \cdot 0 + 4 \cdot 0 = 6\).

Ограничења

• У тест примерима вредним 10 поена: \(n \leq 15\) и \(m \leq 15\).
• У тест примерима вредним 15 поена: \(n \leq 100\) и \(m \leq 100\).
• У тест примерима вредним 20 поена: \(n \leq 600\) и \(m \leq 600\).
• У тест примерима вредним 20 поена: \(n \leq 10000\) и \(m \leq 10000\).
• У тест примерима вредним 35 поена: \(n \leq 100000\) и \(m \leq 10000\).