Problem: You are the owner of a restaurant, and you are serving for N customers seating in a round table.

You will distribute M menus to them. Each customer receiving a menu will make the order of plates, and then pass the menu to the customer on the right unless he or she has not make the order. The customer i takes Li unit time for the ordering.

Your job is to write a program to calculate the minimum time until all customers to call their orders, so you can improve your business performance.



Input

The input consists of a sequence of positive integers.

The first line of the input contains two positive integers N (N ≤ 50,000) and M (M ≤ N). The second line contains N positive integers L1, L2,..., LN (Li ≤ 600).

Output

Output the minimum possible time required for them to finish ordering.

Example

Input




Output

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
using namespace std;
int c[110000];
int sum[110000];
int db[18][110000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
	}
	for(int i=0;i<a;i++)c[a+i]=c[i];
	for(int i=0;i<a*2;i++)sum[i+1]=sum[i]+c[i];
	sum[a*2+1]=999999999;
	int left=0;
	int right=100000000;
	while(left+1<right){
		int M=(left+right)/2;
		for(int i=0;i<a*2;i++){
			db[0][i]=upper_bound(sum,sum+a*2+1,sum[i]+M)-sum-1;
		}
	//	printf("%d\n",M);
	//	for(int i=0;i<a*2;i++)printf("%d ",db[0][i]);printf("\n");
		db[0][a*2]=a*2;
		for(int i=1;i<18;i++){
			for(int j=0;j<=a*2;j++){
				db[i][j]=db[i-1][db[i-1][j]];
			}
		}
		bool ok=false;
		for(int i=0;i<a;i++){
			int at=i;
			for(int j=0;j<18;j++){
				if(b&(1<<j)){
					at=db[j][at];
				}
			}
			if(at>=i+a)ok=true;
		}
		if(ok)right=M;else left=M;
	}
	printf("%d\n",right);
}