Prakhar has a string with \(N\) words where the length of the \(i^{th}\) word is \(L_i\)_.

The words are displayed in the window separated by a space. More precisely, when the sentence is displayed in a window of width \(W\), the following conditions are satisfied.

The first word is displayed at the beginning of the top line.
The \(i^{th}\) word (\(2 \leq i \leq N\)) is displayed either with a gap of \(1\) after the \((i-1)^{th}\) word, or at the beginning of the line below the line containing the \((i-1)^{th}\) word
The width of each line does not exceed \(W\). Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.
A word should not be broken into \(2\) or more lines

Prakhar Wants to fit these words in \(M\) or less than \(M\) lines, find the minimum possible width \(W\) of the window.

Input Format:

The first line contains \(2\) space seperated integers \(N\) - the total number of words and \(M\) - the required number of lines.

The next line contains \(N\) space seperated integers \(L_i\)

Output Format:

Print the minimum possible width \(W\) of the window

Constraints:

\(1 \leq N \leq 2*10^5 \\ 1 \leq M \leq 2*10^5 \\ 1 \leq L_i \leq 10^9\)