petrom

Firma Petrom are n benzinării amplasate de-a lungul autostrăzii Soarelui. Benzinăriile sunt numerotate de la 1 la n în ordinea amplasării pe autostradă.

Poziţiile benzinăriilor sunt cunoscute, fiind specificate prin distanţele $d_1, d_2, …, d_n$ ($d_i$ reprezintă distanţa de la sediul firmei Petrom până la benzinăria i). Sediul firmei Petrom este amplasat la intrarea pe autostrada Soarelui.

În k dintre aceste benzinării firma doreşte să amenajeze depozite de combustibil, care să alimenteze benzinăria respectivă, dar şi alte benzinării învecinate. Fiecare benzinărie va fi alimentată de la depozitul cel mai apropiat.

Costul de transport pentru o amplasare a depozitelor dată va fi egal cu suma distanţelor de la fiecare benzinărie la depozitul de la care se alimentează.

Cerinţă

Scrieţi un program care să determine benzinăriile în care trebuie să construite depozite, astfel încât costul de transport să fie minim.

Date de intrare

Fişierul de intrare petrom.in conţine pe prima linie două numere naturale separate prin spaţiu n şi k, reprezentând numărul de benzinării şi respectiv numărul de depozite care trebuie construite.
Pe următoarele n linii sunt scrise n numere naturale $d_1, d_2, …, d_n$, câte un număr pe o linie, reprezentând distanţele de la sediul Petrom la cele n benzinării.

Date de ieşire

Fişierul de ieşire petrom.out va conţine pe prima linie costul de transport (minim posibil).
Pe următoarele k linii sunt scrise benzinăriile în care vor fi construite depozite pentru a obţine costul minim, câte o benzinărie pe o linie.

Restricţii şi precizări

• 1 ≤ n ≤ 400
• 1 ≤ k ≤ 300
• k ≤ n
• $0 < d_1 < d_2 < … < d_n ≤ 30000$
• Dacă există mai multe soluţii puteţi determina oricare dintre acestea.
• Pentru fiecare test, se acordă 40% din punctaj pentru determinarea costului minim şi 100% pentru rezolvarea integrală.

Exemplu

petrom.in

6 3
5
6
12
19
20
27

petrom.out

8
2
4
6

Explicaţie

Depozitul 1 va fi construit în benzinăria 2 şi alimentează benzinăriile 1, 2, 3. (Cost: 1+0+6=7)
Depozitul 2 va fi construit în benzinăria 4 şi alimentează benzinăriile 4, 5. (Cost: 0+1=1)
Depozitul 3 va fi construit în benzinăria 6 şi alimentează benzinăria 6. (Cost: 0)