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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 50005

int N,M;
ll table[2*NUM];


bool is_ok(ll value,int start_index){

	ll num_section,base,next_base;
	int L,R,mid;

	for(int start = start_index; start <= start_index; start++){

		num_section = 0;
		base = start;

		while(base < N+start){

			//2分探索で、総和がvalue以下となる最大のインデックスを求める
			L = 0,R = start+N-1-base,mid = (L+R)/2;

			while(L <= R){

				if(table[base+mid]-table[base-1] <= value){

					next_base = base+mid+1;
					L = mid+1; //より区間を長く

				}else{

					R = mid-1;
				}
				mid = (L+R)/2;
			}

			num_section++;

			base = next_base;

			//残りを最大化しても、総和が足りなければ不可
			if(value*(M-num_section) < table[start+N-1]-table[base-1]){
				return false;
			}
		}

		if(num_section <= M){
			return true;
		}
	}

	return false; //区間分割数がM以下か
}



int main(){

	scanf("%d %d",&N,&M);

	ll maximum = 0;

	table[0] = 0;
	for(int i = 1; i <= N; i++){

		scanf("%lld",&table[i]);
		table[i+N] = table[i];
		maximum = max(maximum,table[i]);
	}

	for(int i = 1; i <= 2*N; i++){

		table[i] += table[i-1];
	}

	ll L = maximum, R = table[N], mid = (L+R)/2;
	ll ans = BIG_NUM;

	while(L <= R){

		if(is_ok(mid,1)){

			ans = mid;
			R = mid-1;
		}else{

			L = mid+1;
		}

		mid = (L+R)/2;

	}

	L = maximum,R = ans,mid = (L+R)/2;
	int left,right,m,start_index,end_index;

	vector<int> V;

	while(L <= R){

		//2から数えて、合計がmidを超えない最大の右端を求める
		left = 2,right = N+1,m = (left+right)/2;
		end_index = 2;

		while(left <= right){

			if(table[m]-table[1] <= mid){

				end_index = m;
				left = m+1; //より右へ

			}else{

				right = m-1;
			}
			m = (left+right)/2;
		}

		V.clear();
		for(int i = 2; i <= end_index; i++){
			V.push_back(i);
		}

		//左端を求める
		ll tmp_sum = table[end_index]-table[1];

		if(end_index == N+1){

			//Do nothing
		}else{

			left = end_index+1,right = N+1,m = (left+right)/2;
			start_index = N+1;

			while(left <= right){

				if(table[N+1]-table[m-1]+tmp_sum <= mid){

					start_index = m;
					right = m-1; //より左へ

				}else{

					left = m+1;
				}
				m = (left+right)/2;
			}

			for(int i = start_index; i <= N+1; i++){

				V.push_back(i);
			}
		}

		bool FLG = false;

		for(int i = 0; i < V.size(); i++){

			if(is_ok(mid,V[i])){
				FLG = true;
				break;
			}
		}

		if(FLG){ //少なくとも一件成功すれば良し

			ans = mid;
			R = mid-1;

		}else{

			L = mid+1;
		}

		mid = (L+R)/2;
	}

	printf("%lld\n",ans);

	return 0;
}