Zion

Opis zadatka:

U jedinom preostalom ljudskom gradu Zionu ljudi vole da plešu i da se zabavljaju na urnebesnim tehno zabavama. Neo i njegovi prijatelji ovaj put žele da organiziraju nešto posebno.

Posebna atrakcija na takvim zabavama je izvedba popularnog plesa zvanog "vozić". Taj ples se pleše tako da se svi gosti na zabavi poredaju jedan iza drugoga, svako (osim osobe koja je prva u voziću) stavi ruke na ramena osobe ispred sebe, te tada svi razdragano plešuci obilaze cijelu salu.

Naravno, Morpheus želi da taj vozić izgleda što bolje, pa mu smeta kada se u voziću nađu jedan iza drugog ljudi jako različitih visina, što narušava ljepotu i usporava vozić. Pošto na takvim zabavama učestvuju i oficiri i vojska koja brani grad Zion od zlih napada mašina, a znamo da su vojnici jako osjetljivi na rang, ne smije se dogoditi da se u voziću bilo gdje ispred jednog oficira nađe oficir nižeg ranga. Ostali učesnici nemaju posebnih prohtjeva i svejedno im je gdje ce se nalaziti u voziću.

Zadane su visine svih učesnika zabave i poredak oficira po rangu. Potrebno je napisati program koji će odrediti raspored ljudi u voziću tako da nijedan oficir nema ispred sebe nekog oficira nižeg ranga i da pri tome ukupna suma razlika visina izmedu svih susjeda u voziću bude što je god moguće manja.

Izvršna datoteka treba da se nalazi u direktoriju C:\BHOI2003 pod imenom ZION.EXE.

Ulazna datoteka:

Ulazni podaci nalaze se u tekstualnoj datoteci ZION.IN.

U prvom redu ulazne datoteke nalaze se dva prirodna broja N i K međusobno odvojena jednim razmakom. N predstavlja ukupan broj ljudi na zabavi, pri čemu je 1 <= N <= 10000, dok K predstavlja broj oficira odbrane Ziona, pri čemu je 1 <= K <= 1000 i K <= N.

U svakom od sljedećih N redova nalazi se prirodni broj V, 1000 <= V <= 2200, koji predstavlja visinu pojedinog gosta izraženu u milimetrima. Gosti su označeni brojevima od 1 do N, a prvih K gostiju su oficiri poredani po rangu silazno (dakle učesnik označen brojem 1 je oficir sa najvišim rangom, a učesnik označen brojem K je oficir sa najnižim rangom).

Izlazna datoteka:

U prvi i jedini red izlazne tekstualne datoteke ZION.OUT potrebno je zapisati traženu minimalnu sumu razlika visina susjeda u voziću.

Vremensko ograničenje:

Za svaki testni primjer program treba da ponudi rješenje za najviše 20 sekundi.

Primjeri:

ZION.IN
3 2
2000
1200
1500
ZION.OUT
800
ZION.IN
5 3
1900
1300
1500
1200
1600
ZION.OUT
1000
ZION.IN
6 3
1700
1900
1500
1800
1750
1300
ZION.OUT
800

Napomena: Raspored ljudi u voziću ne mora biti jednoznačno određen.

[Testni podaci] [Rješenje (Pascal)] [Rješenje (C++)]