#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define CISHUMAX 105
#define SHITOUMAX 100005
#define MAX 9999999
int f[SHITOUMAX][CISHUMAX];
int weight[SHITOUMAX];
//最大連續和的最小值 PKU 3273 Monthly Expense
//此題用動態規劃會超時，但作為一種方法，不妨記錄下來 
/*
輸入:
8 3
1 2 3 4 5 6 7 8
*/

void cal(int num,int duan)
{
	int i,j,temp,max,k;
	for(i=1;i<=num;i++) 
		f[i][1]=f[i-1][1]+weight[i];
//	print(num,duan);
	for(j=2;j<=duan;j++)
	{	//分成j塊
		for(i=j;i<=num;i++)
		{	//當前石頭個數為i
			temp=MAX;
			for(k=1;k<i;k++)
			{	//k+1,...,i為新塊數的石頭
				if(f[i][1]-f[k][1]<f[k][j-1]) max=f[k][j-1];
				else max=f[i][1]-f[k][1];
				if(max<temp) temp=max;
			}
			f[i][j]=temp;
//			print(num,duan);
		}
	}
}


int main()
{
	int num,duan,i;
	scanf("%d%d",&num,&duan);
	for(i=1;i<=num;i++)
		scanf("%d",&weight[i]);
	cal(num,duan);
	cout<<f[num][duan]<<endl;
	return 0;
}