/*
TASK:bus
LANG:C++
*/
#include<stdio.h>
#define maxn 1024

using namespace std;

void input();
void solve();

int m[maxn];
int f[maxn];

int cost[maxn][maxn];
int dp[maxn][maxn];
int pred[maxn][maxn];
int N, K;

int main()
{
input();
solve();
return 0;
}

void solve()
{
int i, j, x;
int len, c, left;

f[0] = 0;
for(i = 1; i <= N; i++) f[i] = f[i-1] + m[i];
for(i = 1; i <= N; i++) cost[i][i] = 0;

for(i = 1; i <= N; i++)
      for(j = i + 1; j <= N; j++)
            {
            len = j - i + 1;
            c = len / 2;
            left = i + c;
            cost[i][j] = cost[i][j-1] + f[j-1] - f[left-1];
            }
/*
for(i = 1; i <= N; i++)
      {
      for(j = 1; j <= N; j++)
            printf("%2d ", cost[i][j]);
      printf("\n");
      }
*/

for(i = 1; i <= N; i++) dp[2][i] = cost[1][i];
for(i = 1; i <= K; i++) pred[i][0] = 1;

//freopen("bus.out", "w", stdout);
for(i = 3; i <= K; i++)
      for(j = 1; j <= N; j++)
            {
            dp[i][j] = 2000000000;
//            printf("calculating dp[%d][%d], starting with %d\n", i, j, pred[i][j-1]);
            for(x = pred[i][j-1]; x <= j; x++)
                  {
                  c = dp[i-1][x] + cost[x][j];
                  if(dp[i][j] > c)
                              {
                              dp[i][j] = c;
                              pred[i][j] = x;
                              }
                  }
            }
            
printf("%d\n", dp[K][N]);
}



void input()
{
//freopen("bus.in", "r", stdin);
scanf("%d%d", &N, &K);
for(int i = 1; i <= N; i++) scanf("%d", &m[i]);
}

      
