using namespace std;
#include <bits/stdc++.h>

int minLenNeeded(vector<int>& wordLen, int n) {

    int sum = wordLen.size()-1;
    int longWord = 0;
    for (int i=0; i<wordLen.size(); i++) {
        sum += wordLen[i];
        longWord = max(longWord, wordLen[i]);
    }
    int low = longWord, high = sum;

    while (low<high) {

        int mid = (low+high)/2;

        int numLines = 0, curLen = 0;
        for (int i=0; i<wordLen.size(); i++) {

            // Get new line length.
            int nextLen = curLen + wordLen[i];
            if (curLen > 0) nextLen++;

            if (nextLen > mid) {
                numLines++;
                curLen = wordLen[i];
            }
            else
                curLen = nextLen;
        }
        if (curLen>0) numLines++;

        if (numLines <= n)
            high = mid;
        else
            low = mid+1;
    }

    return low;
}

int main() {

    vector<int> words = {10,3,8,5,6,7,2};
    cout << minLenNeeded(words, 2) << endl;
    cout << minLenNeeded(words, 3) << endl;
    return 0;
}