Dobili ste posao magacionera u novom magacinu kutija! Magacin je ogroman i u njemu se nalazi n gomila kutija, u svakoj gomili su kutije poređane jedna na drugu. Međutim, neke gomile su previsoke a neke preniske, a vi volite red, pa ste rešili da prerasporedite neke kutije.

Na raspolaganju vam je viljuškar koji odjednom može da prenosi tačno k kutija (ni manje ni više). Prema tome, u jednom prebacivanju možete uzeti tačno k kutija sa neke gomile (koja ima bar k kutija) i prebaciti ih na bilo koju drugu gomilu. Želite da izvršite nekoliko prebacivanja tako da na kraju dobijete n što približnijih gomila, tj. da razlika broja kutija na najvećoj i najmanjoj gomili bude minimalna. Odredite tu razliku.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj gomila i kapacitet viljuškara (1 ≤ n, k ≤ 10⁶). Sledeći red sadrži n brojeva a_i razdvojenih razmakom - broj kutija na odgovarajućim gomilama (1 ≤ a_i ≤ 10⁹).

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlazne datoteke ispisati minimalnu moguću razliku između broja kutija na najvećoj i najmanjoj gomili posle optimalnog niza prebacivanja.

Primer:

5 7
20 3 8 19 29

6

Objašnjenje.

Ukoliko prebacimo 7 kutija sa prve na drugu gomilu, 7 kutija sa pete na drugu i 7 kutija sa pete na treću, dobijamo gomile 13 17 15 19 15 gde je razlika između najveće i najmanje 19 - 13 = 6. Nijedan drugi niz prebacivanja ne daje manju razliku.