Baštovan Toma je rešio da ulepša svoje prostrano dvorište tako što će ga ukrasiticvećem. On naime želi da najpre postavi n saksija u red (1 ≤ n ≤ 1000000) i da u svakoj odovih n saksija bude k kilograma zemlje (0 ≤ k ≤ 1000), a da potom u njima sadi raznoraznocveće. On je zato od firme koja se bavi prodajom saksija naručio n saksija takvih da se usvakoj od tih n saksija nalazi k kilograma zemlje. Ta firma je bila toliko ljubazna da mune samo donese te saksije već i da ih postavi u red. Međutim, sutradan je Toma doživeoveliki šok. Neke saksije imaju više, a neke manje od k kilograma zemlje. Toma se ipak malosmirio kada je primetio da je ukupna težina zemlje u svim saksijama k · n kilograma - pa seipak ova greška da ispraviti. Toma želi da prebacivanjem zemlje iz jedne u drugu saksijuučini da u svakoj saksiji bude k kilograma zemlje, a da se pri tome najmanje umori. Tomazna da za prebacivanje x kilograma zemlje iz saksije koja je i-ta po redu u saksiju koja jej-ta po redu utroši x · |i - j| džula energije. Odrediti koliko je minimalno energije kojuToma mora potrošiti da bi ispravio grešku firme koja mu je prodala saksije.
Ulaz:
(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu tekstualne datotekenalaze se redom celi brojevi n i k. U drugom redu ove datoteke nalazi se n celih brojevakoji su veći ili jednaki 0. Naime i-ti broj (1 ≤ i ≤ n) u drugom redu označava koliko sekilograma zemlje nalazi u i-toj saksije kada se gleda sa prozora Tomine spavaće sobe saleva na desno.
Izlaz:
(Izlazni podaci se ispisuju na standardni izlaz) U izlaznu datoteku treba upisatijedan 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.
Primer:
standardni ulaz | standardni izlaz | |
---|---|---|
6 4 5 6 2 1 7 3 |
8 |
Comments