Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called “fajomonths”. Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ’s goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input
Line 1: Two space-separated integers: N and M
Lines 2… N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day
Output
Line 1: The smallest possible monthly limit Farmer John can afford to live with.
Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

这道题目题意可以简化为在m个数中寻找n个小区间，使这n个小区间的每个区间和的最大值存在一个最小值，并输出该最小值。

我们可以使用二分的思路来进行解题，我们可以先求出一天（耗费最多的那天）的花费作为left，因为我们无论如何划分区间，这个值都只能是小于等于我们要求的值（该值单独作为一个小区间时结果为该值）。另外我们再把这些花费的总和作为right（最大不会超过该值）。这样我们在left与right之间进行二分。

在进行二分时我们可以对计算的小区间个数进行计数（注意每次到最后时都要加上最后的花费区间），然后我们对我们得到的区间数与给定的区间数进行比较，当我们的区间数小于给定的区间数时证明我们的中间取值大了，这时进行 right=mid;，反之则left=mid+1;最后确定mid值。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100001;
int money[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int left=-1,right=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&money[i]);
        if(left<money[i])            //left反而用来记录最大值（至少为一天，故一定存在比该最值大于等于的时候（最小值为该最大值））
            left=money[i];
        right+=money[i];             //right为所有数据的和，即sum（花费）
    }
    while(left<right)
    {
        int mid=(left+right)/2;
        int cnt=0;
        int cost=0;
        for(int i=1;i<=n;i++)
        {
            if(cost+money[i]>mid)
            {
                cnt++;//划分区间，不包括当前的money[i]
                cost=money[i];
            }
            else
                cost+=money[i];
        }
        cnt++;//最后一个cost值也要占一天
        if(cnt<=m)
            right=mid;
        else
            left=mid+1;
    }
    cout<<right<<endl;
    return 0;
}