Micul Gigel se joacă cu N turnuri, fiecare turn fiind format din unul sau mai multe cuburi aşezate unul peste altul. Pentru fiecare turn se defineşte înălţimea lui ca fiind numărul de cuburi care îl formează. Pentru a-i transforma jocul într-o provocare intelectuală, învăţătoarea lui Gigel îi recomandă acestuia să aleagă exact K înălţimi standard şi să reconstruiască turnurile astfel încât noile lor înălţimi să se găsească printre înălţimile standard. Gigel ştie că pentru a elimina un cub dintr-un turn (micşorându-i astfel înălţimea cu o unitate) sau pentru a aşeza un cub la vârful turnului (mărindu-i înălţimea cu o unitate) are nevoie de un minut. Pentru că lucrul la un singur turn poate deveni monoton, Gigel doreşte să aleagă înălţimile standard astfel încât timpul maxim necesar pentru a modifica un turn sa fie cât mai mic posibil.

Cerinta

Scrieţi un program care să determine exact K înălţimi standard astfel încât timpul maxim necesar pentru a modifica un turn să fie minim posibil.

Date de intrare

Fişierul de intrare standard.in conţine pe prima linie două numere naturale N şi K, separate printr-un spaţiu, reprezentând numărul de turnuri şi respectiv numărul de înălţimi standard care trebuie alese. Cea de a doua linie conţine N numere naturale nenule în ordine strict crescătoare, separate prin câte un spaţiu, reprezentând înălţimile celor N turnuri.

Date de iesire

Fişierul de ieşire standard.out va conţine pe prima linie timpul maxim T necesar pentru a modifica un turn, pe cazul optim. Următoarea linie conţine K numere naturale, reprezentând înălţimile standard alese. Dacă sunt mai multe soluţii pentru acelaşi timp T se va afişa cea în care şirul înălţimilor este minim lexicografic.

Restrictii

• 1 <= K <= N <= 100 000
• Înălţimile turnurilor şi înălţimile standard vor fi numere naturale nenule mai mici de 2 miliarde
• Înălţimile standard determinate trebuie să fie distincte două câte două
• Înălţimile standard nu trebuie să se afle obligatoriu printre înălţimile iniţiale ale turnurilor
• Spunem că şirul x = (x₁ x₂ … x_k) este mai mic lexicografic decât şirul y = (y₁ y₂ … y_k) dacă există un indice i, cu 1 <= i <= k, astfel încât x_i < y_i şi x_j = y_j, pentru orice 0 < j < i

Exemplu

standard.in	standard.out	Explicatie
6 2 5 7 9 16 20 31	6 10 25	La primul turn se vor adauga 5 cuburi. La al doilea turn se vor adăuga 3 cuburi. La al treilea turn se va adăuga 1 cub. Din al patrulea turn se vor elimina 6 cuburi. La al cincilea turn se vor adăuga 5 cuburi. Din al şaselea turn se vor elimina 6 cuburi.

Filip Cristian Buruiana

stud. Facultatea de Automatica si Calculatoare, Universitatea Politehnica, Bucuresti

filipb2001@yahoo.com