Perica je oduvek voleo igre na sreću, pa je smislio jednu za svog druga Jovicu. Perica uzme n papirića, na svakom papiriću napiše po jedan broj i okrene ih tako da Jovica ne zna koji su brojevi napisani. Zatim Jovica mora da rasporedi sve papiriće na proizvoljan broj gomila. Svaka gomila mora da ima najmanje 2, a najviše k papirića. Na kraju Perica otkrije sve papiriće, te računa broj poena koji je Jovica osvojio.

Perica računa poene na sledeći način: Pronađe najveći i najmanji broj na jednoj gomili i izračuna njihovu razliku. Kada izračuna razliku najvećeg i najmanjeg za svaku gomilu, sabere sve razlike. Dobijena vrednost predstavlja osvojene poene. Što je broj poena manji, to je Jovica uspešniji.

Znajući koje brojeve je Perica napisao na papiriće, odredite koliko najmanje poena Jovica može da sakupi.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke papirici.in.) U prvom redu ulaza nalaze se dva broja n i k (2 ≤ k ≤ n ≤ 100.000) koji predstavljaju, redom, broj papirića i maksimalnu veličinu gomila. U drugom redu se nalazi n celih brojeva, koji predstavljaju brojeve napisane na papirićima. Svi brojevi će biti u intervalu [-2³¹, 2³¹ - 1].

Izlaz:

(Izlazni podaci se ispisuju u datoteku papirici.out.) U prvom i jedinom redu izlaza ispisati najmanji broj poena koji može da se sakupi. Rešenje će uvek postojati.

Primer:

7 3
6 0 5 2 8 0 -2

7

Objašnjenje.

Na prvu gomilu se stave papirići sa brojevima 0 i 2, na drugu gomilu papirići sa 6, 5 i 8, a na treću papirići sa 0 i -2. Ukupan broj poena je (2 - 0) + (8 - 5) + (0 - (-2)) = 7

Napomena.

U 30% test primera biće k ≤ 100.

/*
  Autor: Vanja Petrovic Tankovic
*/
#include <cstdio>
#include <algorithm>

#define INF 1000000000000ll
#define MAXN 100001

using namespace std;

int n,k,niz[MAXN];
long long razlika[MAXN],resenje;

int main()
{
  freopen("papirici.in","r",stdin);
  freopen("papirici.out","w",stdout);  
 
  scanf("%d %d",&n,&k);
  for (int i=0; i<n; i++)
    scanf("%d",&niz[i]);
  sort(niz,niz+n);    
  
  if (k==2)
    for (int i=0; i<n; i+=2)
      resenje+=(long long)niz[i+1]-niz[i];
  else    
  {
    razlika[0]=INF;
    razlika[1]=(long long)niz[1]-niz[0];
    razlika[2]=(long long)niz[2]-niz[0];
    for (int i=3; i<n; i++)
      if (razlika[i-2]-niz[i-1]<razlika[i-3]-niz[i-2])
        razlika[i]=(long long)niz[i]-niz[i-1]+razlika[i-2];
      else
        razlika[i]=(long long)niz[i]-niz[i-2]+razlika[i-3];  
    resenje=razlika[n-1]; 
  }
  
  printf("%u",resenje);
  return 0;  
}