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 d1, d2, …, dn (di 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 d1, d2, …, dn, 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
1 ≤ n ≤ 400
1 ≤ k ≤ 300
k ≤ n
0 < d1 < d2 < … < dn ≤ 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ă.
Exemple
petrom.in
petrom.out
Explicaţii
6 3
5
6
12
19
20
27
8
2
4
6
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)