Simulation - Lot 2014 Baraj 3 Juniori | orase

Cerință

Pe axa reală există $N$ orașe, numerotate cu numerele $1, 2, 3, \dots, 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ă.

Date de intrare

În fișierul orase.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$.

Date de ieșire

Fișierul orase.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.

Restricții și precizări

• $2 \leq N \leq 1 \ 000 \ 000$
• $1 \leq K \leq \min(N, 1 \ 000)$
• suma celor $N - 1$ distanțe nu depășește $2 \ 000 \ 000 \ 000$
• $30\%$ dintre teste vor avea $N \leq 1 \ 000$

Exemplu

orase.in

7 3
3 1 4 14 4 3

orase.out

4 2

Explicație

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