FRAKTAL - konkurs programistyczny

Andrzej uczy n uczniów algorytmiki. Każdy uczeń posiada pewien poziom wiedzy p_i.

Nasz bohater chciałby podzielić swoich uczniów na m grup. Do każdej z m grup musi zostać przydzielony minimum 1 uczeń. Zdefiniujmy sobie poziom problematyczności jako różnicę poziomu wiedzy najlepszego i najsłabszego ucznia w grupie. Andrzej chciałby, aby po podziale na m grup, suma poziomów problematyczności była minimalna.

Odpowiedz na pytanie, ile wynosi minimalna suma poziomów problematyczności jaką może uzyskać Andrzej?

Wejście

W pierwszej linii wejścia znajduje się liczba uczniów n ∈ [1, 8000] oraz liczba grup m ∈ [1, n].

W drugiej linii wejścia znajduje się n liczb naturalnych p_i ∈ [1, n], określających poziom wiedzy każdego z uczniów naszego bohatera.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile wynosi minimalna suma poziomów problematyczności jaką może uzyskać Andrzej.

Przykład

Wejście:

8 3
8 7 1 3 5 5 4 1

Wyjście:

3

Wyjaśnienie do przykładu:

Optymalny podział na grupy wygląda następująco:

• 8 7
• 3 5 5 4
• 1 1

Poziom problematyczności powyższych grup wynosi odpowiednio: 1, 2, 0