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$