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. \InputFile 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$. \OutputFile Print the minimum possible sub-array sum. \includegraphics{https://static.e-olymp.com/content/fa/fa4249eaba38a60e358e745a9a784883ce10a68c.gif} \Example 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.