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 k niech A(k) będzie taką liczbą, że wśród gmin o kolorze k:

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

Zadanie

Napisz program, który:

• wczyta z pliku wejściowego MAP.IN zaludnienia gmin Bajtocji,
• obliczy minimalny błąd sumaryczny,
• zapisze wynik w pliku tekstowym MAP.OUT.

Wejście

W pierwszym wierszu pliku wejściowego MAP.IN znajduje się jedna liczba całkowita n równa liczbie gmin Bajtocji, 10< n <3000. W drugim wierszu jest zapisana liczba m kolorów użyta do pokolorowania mapy, 2 <= m <= 10. W każdym z następnych n wierszy znajduje się po jednej nieujemnej liczbie całkowitej. Są to zaludnienia gmin Bajtocji. Zaludnienie nie przekracza 2^³⁰.

Wyjście

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

Przykład

Dla pliku wejściowego MAP.IN:

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

15