Split into k sub-arrays

Given array of $n$ elements and number $k$. Split the given array into $k$ sub-arrays (they must cover all the elements). The maximum sub-array sum achievable out of $k$ sub-arrays formed, must be minimum possible. Find that possible sub-array sum.

Input

First line contains two numbers $n$ and $k(n\le 10^6,1\le k\le n)$. Second line contains $n$ positive integers, each no more than $10^9$.

Output

Print the minimum possible sub-array sum.

Examples

For the first sample the optimal split is $\{1,2\},\{3\},\{4\}$. Maximum sum of all sub-arrays is $4$, which is minimum possible for $3$ subarrays.

For the second sample the optimal split is $\{1,2,3,4\},\{2,3,4\},\{2,3,1\}$. Maximum sum of all sub-arrays is $10$, which is minimum possible for $3$ subarrays.