#include<bits/stdc++.h>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
inline int rd(){
	int xx=0;char ch=getchar(),flag=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		xx=xx*10+ch-'0';
		ch=getchar();
	}
	return xx*flag;
}
int n,m,x,maxx;
long long a[3000050];
inline char test(long long mx){
	int fm=0,p;//cout<<mx<<':';
	for(int i=1;i<=m;i++){
		long long zhi=a[fm]+mx;p=1;
		while(a[fm+p]<=zhi){fm+=p;p<<=1;}
		p>>=1;
		while(p){
			if(a[fm+p]<=zhi)fm+=p;
			p>>=1;
		}
		//cout<<fm<<' ';
		if(fm>=n)break;
	}
	//cout<<'\n';
	return fm>=n;
}
int main(){
	//freopen("1.in","r",stdin); 
	n=rd(),m=rd();
	memset(a,0x3f,sizeof(a));a[0]=0;
	for(int i=1;i<=n;i++){
		x=rd();
		a[i]=(long long)x+a[i-1];
		maxx=max(maxx,x);
	}
	long long l=maxx,r=a[n],mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(l+1>=r){
			if(test(l))break;
			else {
				l=r;break;
			}
		}
		if(test(mid))r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
	//cout<<(int)test(106117);
	return 0;
}

这样最优可低到(logn)^2,即使m略小于n,也不会慢多少,也可以为nlogn。