A gas station too far P23800

There is just one road connecting the $n+1$ cities $c_0, \dots, c_n$ consecutively. You want to go from $c_0$ to $c_n$ stopping at most $s$ times to fill the tank of the car. There are gas stations at the cities, but none on the roads. The length of each road is $\ell_0, \dots, \ell_{n-1}$. Which is the minimum range for your car? Suppose that you start with a full tank.

Input

Input consists of several cases. Every case begins with $n$ and $s$, which are followed by $n$ natural numbers $\ell_0, \dots, \ell_{n-1}$. Suppose $1 \le n \le 10^5$, $0 \le s \le n - 1$, and $1 \le \ell_i \le 10^4$.

Output

For every case, print the minimum range for a car to reach $c_n$ starting from $c_0$ stopping at most $s$ times to fill the tank.

Hint

Consider a decisional version of this problem.