Nosaukums
Pasta nodaļas (post)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Taisna lielceļa malā atrodas ciemati. Lielceļu attēlosim kā naturālu skaitļu asi un katra ciemata koordinātu kā kādu naturālu skaitli uz šīs ass. Nekādi divi ciemati neatrodas uz ass vienā un tajā pašā vietā. Attālums starp diviem ciematiem ir šo ciematu koordinātu starpības absolūtā vērtība.

Jāuzbūvē pasta nodaļas vairākos, bet ne obligāti visos ciematos. Ciematam un šajā ciematā uzbūvētai pasta nodaļai ir viena un tā pati koordināta. Būvējot pasta nodaļas, ciemati jāizvēlas tā, lai attālumu summa no katra ciemata līdz tam tuvākajai pasta nodaļai būtu pēc iespējas mazāka.

Uzrakstiet programmu, kas, dotām visu ciematu koordinātām un uzbūvējamo pasta nodaļu skaitam, aprēķina mazāko iespējamo attālumu summu no katra ciemata līdz tam tuvākajai pasta nodaļai.


Ievaddatu raksturojums

Ievaddatu faila vārds ir post.in. Faila pirmajā rindā ir doti divi naturāli skaitļi: ciematu skaits V, 1<=V<=300, un pasta nodaļu skaits P, 1<=P<=30, P<=V. Faila otrajā rindā doti V naturāli skaitļi - ciematu koordinātas augošā secībā. Katrai koordinātai X ir spēkā sakarība 1<=X<=10000.


Izvaddatu raksturojums

Izvaddatu faila vārds ir post.out. Faila pirmajā rindā jāizvada viens vesels skaitlis, kas ir mazākā iespējamā attālumu summa no katra ciemata līdz tam tuvākajai pasta nodaļai. 


Piezīmes

Pirmajā piemēra testa gadījumā ciematu koordinātas ir 2, 7, 22, 44 un 50.

 
Uzdevums izmantots 12. Vispasaules informātikas olimpiādē Pekinā (Ķīnas TR) 2000.gadā.


Paraugdati

Stdin
10 5
1 2 3 6 7 9 11 22 44 50
Stdout
9

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.