Mapa

Limit pamięci: 32 MB

Po nowym podziale administracyjnym Bajtocji przygotowywana jest mapa demograficzna kraju. Z powodów technicznych do kolorowania mapy można użyć tylko kilku kolorów. Mapę należy pokolorować w taki sposób, żeby gminy o zbliżonym zaludnieniu (tj. liczbie mieszkańców) były pokolorowane tym samym kolorem. Dla danego koloru niech będzie taką liczbą, że wśród gmin o kolorze :

• co najmniej połowa gmin o kolorze ma zaludnienie nie większe od
• co najmniej połowa gmin o kolorze ma zaludnienie nie mniejsze od

Błędem pokolorowania gminy pokolorowanej kolorem nazywamy wartość bezwzględną różnicy liczby i zaludnienia gminy. Błędem sumarycznym nazywamy sumę wszystkich błędów pokolorowania. Jak pokolorować mapę, żeby błąd całkowity był najmniejszy?

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia zaludnienia gmin Bajtocji,
• obliczy minimalny błąd sumaryczny,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita równa liczbie gmin Bajtocji, . W drugim wierszu jest zapisana liczba kolorów użyta do pokolorowania mapy, . W każdym z następnych wierszy znajduje się po jednej nieujemnej liczbie całkowitej. Są to zaludnienia gmin Bajtocji. Zaludnienie nie przekracza .

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą będącą równą minimalnemu błędowi sumarycznemu, jaki można uzyskać przy kolorowaniu mapy.

Przykład

Dla danych wejściowych:

11
3
21
14
6
18
10
2
15
12
3
2
2

poprawną odpowiedzią jest:

15

Autor zadania: Marcin Sawicki.