Mali Tom je bio nevaljao, i za kaznu je dobio zaduženje da ofarba zid. Zid se može predstaviti kao matrica sa ~N~ vrsta i ~M~ kolona. Tom ima jako čudnu četku kojom može u ~i~-toj vrsti da ofarba ili prvih ~A_i~ kolona ili poslednjih ~M-A_i~ kolona. Tomu je svaka kolona dosadna onoliko koliko iznosi proizvod broja ofarbanih i neofarbanih polja u toj koloni. Ukupna dosadnost zida je jednaka zbiru dosadnosti svih kolona. Pomozite Tomu i izračunajte najmanju moguću dosadnost zida nakon bojenja.

Opis ulaza

U prvoj liniji standardnog ulaza se nalaze dva cela broja, ~N~ i ~M~, koja predstavljaju broj vrsta i broj kolona, U narednih ~N~ linija se nalazi po jedan ceo broj, ~A_i~, koji predstavlja granicu za farbanje ~i~-te vrste (~0 \leq A_i \leq M~).

Opis izlaza

U jedinoj liniji standardnog izlaza se nalazi jedan ceo broj koji predstavlja minimalnu dosadnost zida nakon farbanja.

Primer 1

Ulaz

2 3
1
2

Izlaz

1

Primer 2

Ulaz

4 4
2 
1 
4 
1

Izlaz

6

Objašnjenje primera

U prvom primeru je najbolje ofarbati obe vrste sa desne strane i onda bi ukupna dosadnost bila ~2 \cdot 0 + 1 \cdot 1 + 0 \cdot 2 = 1~.

.##
..#

U drugom primeru je najbolje prvu, drugu i četvrtu vrstu ofarbati sa leve strane, a treću sa desne (pošto je ~A_3 = M~ ona će onda ostati neofarbana).

##..
#...
....
#...

Ukupna dosadnost je ~1 \cdot 3 + 3 \cdot 1 + 4 \cdot 0 + 4 \cdot 0 = 6~.

Ograničenja

• U test primerima vrednim 10 poena: ~n \leq 15~ i ~m \leq 15~.
• U test primerima vrednim 15 poena: ~n \leq 100~ i ~m \leq 100~.
• U test primerima vrednim 20 poena: ~n \leq 600~ i ~m \leq 600~.
• U test primerima vrednim 20 poena: ~n \leq 10000~ i ~m \leq 10000~.
• U test primerima vrednim 35 poena: ~n \leq 100000~ i ~m \leq 10000~.