== include(page="template/taskheader" task_id="orase1") ==

Pe axa reală există $N$ oraşe, numerotate cu numerele 1, 2, 3, …, $N$. Deşi într-o lume unidimensională lucrurile par a fi mult mai simple, totuşi majoritatea locuitorilor sunt nemulţumiţi de distanţele mari parcurse între oraşe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot şi s-a decis promovarea a cel mult $K$ oraşe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteţ, în aşa fel încât distanţa maximă calculată dintre distanţele de la fiecare oraş la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se doreşte să se amplaseze un număr cât mai mic de centre administrative astfel încât  distanţa maximă să nu fie modificată.

Pe axa reală există $N$ oraşe, numerotate cu numerele 1, 2, 3, …, $N$. Deşi într-o lume unidimensională lucrurile par a fi mult mai simple, totuşi majoritatea locuitorilor sunt nemulţumiţi de distanţele mari parcurse între oraşe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot şi s-a decis promovarea a cel mult $K$ oraşe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteţ, în aşa fel încât distanţa maximă calculată dintre distanţele de la fiecare oraş la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se doreşte să se amplaseze un număr cât mai mic de centre administrative astfel încât distanţa maximă să nu fie modificată.

h2. Date de intrare