saksije

Baštovan Toma je rešio da ulepša svoje prostrano dvorište tako što ?e ga ukrasiti cve?em. On naime želi da najpre postavi n saksija u red (1 ? n ? 1000000) i da u svakoj od ovih n saksija bude k kilograma zemlje (0 ? k ? 1000), a da potom u njima sadi raznorazno cve?e. On je zato od firme koja se bavi prodajom saksija naru?io n saksija takvih da se u svakoj od tih n saksija nalazi k kilograma zemlje. Ta firma je bila toliko ljubazna da mu ne samo donese te saksije ve? i da ih postavi u red. Me?utim, sutradan je Toma doživeo veliki šok. Neke saksije imaju više, a neke manje od k kilograma zemlje. Toma se ipak malo smirio kada je primetio da je ukupna težina zemlje u svim saksijama k · n kilograma - pa se ipak ova greška da ispraviti. Toma želi da prebacivanjem zemlje iz jedne u drugu saksiju u?ini da u svakoj saksiji bude k kilograma zemlje, a da se pri tome najmanje umori. Toma zna da za prebacivanje x kilograma zemlje iz saksije koja je i-ta po redu u saksiju koja je j-ta po redu utroši x · |i - j| džula energije. Odrediti koliko je minimalno energije koju Toma mora potrošiti da bi ispravio grešku firme koja mu je prodala saksije.<br><br>

Ulaz:<br><br>

(Ulazni podaci se ucitavaju sa standardnog ulaza) U prvom redu nalaze se redom celi brojevi n i k. U drugom redu ove datoteke nalazi se n celih brojeva koji su ve?i ili jednaki 0. Naime i-ti broj (1 ? i ? n) u drugom redu ozna?ava koliko se kilograma zemlje nalazi u i-toj saksije kada se gleda sa prozora Tomine spava?e sobe sa leva na desno.<br><br>

Izlaz:<br><br>

(Izlazne podatke ispisati na standardni izlaz) Na standardni izlaz treba upisati jedan broj koji je jednak W mod 1000000000, gde je W jednak minimalnom broju Džula koje Toma mora potrošiti da bi ispravio grešku firme od koje je kupio saksije.<br><br>

Primeri:<br><br>
Ulaz:<br>
6 4<br>
5 6 2 1 7 3<br>
Izlaz:<br>
8<br>