#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int MAXV=;

 const int MAXP=;

 const int INF=0x7fffffff;

 int v,p;

 int dis[MAXV],sum[MAXV],w[MAXV][MAXV];//w[i][j]表示在[i,j]间建立一个邮局的最小代价

 int s[MAXV][MAXP],dp[MAXV][MAXP];

 void init()

 {

     scanf("%d%d",&v,&p);

     sum[]=;

     for (int i=;i<=v;i++) scanf("%d",&dis[i]);

     sort(dis+,dis+v+);

     for (int i=;i<=v;i++) sum[i]=dis[i]+sum[i-];

     for (int i=;i<=v;i++)

     {

         w[i][i]=;

         for (int j=i+;j<=v;j++)

         {

             if ((i+j)%==) w[i][j]=sum[j]-sum[(i+j)/]-sum[(i+j)/-]+sum[i-];

                 else w[i][j]=sum[j]-sum[(i+j)/]-sum[(i+j)/-]+sum[i-]-dis[(i+j)/];

         }

     }

 }

 void solve()

 {

     memset(dp,,sizeof(dp));

     for (int i=;i<=v;i++) dp[i][]=w[][i];

     for (int j=;j<=p;j++)

     {

         s[v+][j]=v-;

         for (int i=v;i>=j;i--)

         {

             for (int k=s[i][j-];k<=s[i+][j];k++)

             {

                 if (dp[i][j]>dp[k][j-]+w[k+][i])//一开始这里敲成了w[k+1][j]

                 {

                     dp[i][j]=dp[k][j-]+w[k+][i];

                     s[i][j]=k;

                 }

             }

         }

     }

     printf("%d",dp[v][p]);

 }

 int main()

 {

     init();

     solve();

     return ;

 }