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

Poveste şi cerinţă...

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

Fişierul de intrare $orase1.in$ ...

În fişierul $orase1.in$, pe prima linie se află separate prin spaţii numerele $N$ şi $K$. Pe linia următoare se află $N$ - 1 numere naturale nenule, separate prin spaţii, al i-lea număr reprezentând distanţa dintre oraşele i şi i + 1.

h2. Date de ieşire

În fişierul de ieşire $orase1.out$ ...

Fişierul $orase1.out$ va trebui să conţină pe o singură linie, separate prin spaţiu, două numere naturale, reprezentând distanţa maximă corespunzătoare unei amplasări optime a centrelor, respectiv numărul oraşelor ce trebuie promovate.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ $N$ ≤ 1000000$
* $1 ≤ $K$ ≤ min(N, 1000)$
* $suma celor N-1 distanţe nu depăşeşte 2 000 000 000$
* $30% dintre teste vor avea $N$ ≤ 1 000$

h2. Exemplu
table(example). |_. orase1.in |_. orase1.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 3
  3 1 4 14 4 3
| 4 2

|
h3. Explicaţie

...

O posibilitate de amplasare optimă a centrelor poate fi în oraşele 3 şi 6.

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