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 <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n, m;
vector<int> sum;


int check(int x, int mid){
	int t = x;
	int mindif = INT_MAX;
	int minindex = -1;

	for(int k = 0; k < m; ++k){
		int u = upper_bound(sum.begin(), sum.end(), sum[t] + mid)
				 - sum.begin() - 1;

		if(mindif > u - t){
			mindif = u - t;
			minindex = t;
		}

		t = u;
		if(t - x >= n){
			return minindex;
		}
	}
	return -1;
}


int binsearch(int x, int left, int right){
	while(left < right){
		int mid = (left + right) / 2;
		if( check(x, mid) >= 0 ){
			right = mid;
		}
		else{
			left = mid + 1;
		}
	}
	return left;
}


int main(){
	scanf("%d%d", &n, &m);
	vector<int> L(n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &L[i]);
	}

	sum.resize(3 * n + 1);
	int k = 0;
	for(int i = 0; i < 3; ++i)
	for(int j = 0; j < n; ++j){
		sum[k+1] = sum[k] + L[j];
		++k;
	}

	k = binsearch(0, 1, sum[n]);
	int upb = k;
	int from = check(0, upb);

	for(int i = from; sum[i] - sum[from] <= k; ++i){
		upb = binsearch(i, 1, upb);
	}
	
	printf("%d\n", upb);
}