Se considera n gramezi de piese de remi, fiecare gramada continând un numar dat de piese. Gramezile sunt asezate pe masa în linie, una lânga cealalta, cu spatii între ele. Toate piesele trebuie asezate în k grupe egale, numarul total al pieselor permitând acest lucru.
Însa regula jocului spune ca o grupa va putea fi formata dintr-o gramada initiala sau prin punerea la un loc a doua sau mai multe gramezi vecine (succesive). Cum procedeul nu permite mutarea unor piese dintr-o gramada în alta, este posibil sa nu se poata obtine acelasi numar de piese în fiecare grupa, la sfârsit calculându-se o penalizare în felul urmator:
- pentru fiecare grupa penalizarea este data de numarul de piese suplimentare sau numarul de piese lipsa din grupa respectiva fata de numarul de piese dorit.
- penalizarea totala este suma penalizarilor pentru cele k grupe construite.
Astfel, daca se considera 7 gramezi cu 12, 9, 2, 11, 15, 5 si respectiv 2 pietre si daca se cere realizarea a 4 grupe, este de dorit sa obtinem 14 piese în fiecare grupa. Unind gramezile 1, 2 si 3 si gramezile 6 si 7 se obtin grupele de 23, 11, 15 si respectiv 7 piese. Penalizarile vor fi 9 ( 23-14 ), 3 ( 14-11 ), 1 ( 15-14 ) si 7 ( 14-7 ), iar penalizarea totala : 9 + 3 + 1 + 7 = 20.

Cerinta

Scrieti un program care sa determine o modalitate de grupare a gramezilor astfel încât penalizarea totala sa fie minima.

Date de intrare

Fisierul de intrare remi.in contine:
- pe prima linie valorile întregi n si k despartite printr-un spatiu;
- pe linia a doua n numere întregi (cu valori cuprinse între 0 si 255) reprezentând numarul de piese din fiecare gramada; numerele sunt despartite prin câte un spatiu si au proprietatea ca suma lor este divizibila cu k.

Date de iesire

Fisierul de iesire remi.out va contine pe prima linie penalizarea totala corespunzatoare gruparii alese.

Restrictii

n, k numere naturale, 1 <= k <= n <= 80

Exemple

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:ema at mail.dntis.ro