Problem Statement

One day, the $K$ magical girls including Rho received from Ultimate Thistle a ring made of $N$ linked beads.
Each of the $N$ beads is numbered $1,2,\dots,N$.
The $i(2 \leq i \leq N-1)$-th bead is adjacent to beads $i-1$ and $i+1$, the $1$-st bead is adjacent to beads $N$ and $2$, and the $N$-th bead is adjacent to beads $N-1$ and $1$.

Ultimate Thistle has infused these beads with magical power, and each one has a value depending on the quality of its magical power.
Specifically, the value of the $i$-th bead is $A_i$.

They decided to divide this ring into $K$ segments consisting of consecutive beads and share them among the $K$ of them.
However, an unequal division would lead to conflict, so, letting $M$ be the minimum of the total values of the beads in each share, they decided to divide the ring so that $M$ is maximized.

Now, as their mascot, you have decided to find $M$ for such a division in order to guide them from the shadows.

Input

$N\ K$
$A_1\ A_2\ \dots\ A_N$

All inputs are integers.
$1\leq K\leq N\leq 10^5$
$1\leq A_i\leq 10^9 (1\leq i\leq N)$

Output

Print the maximum value of $M$. Print a newline at the end.

Sample

6 4
8 6 9 1 2 1

4

15 7
12 9 11 15 15 11 9 7 2 3 1 14 15 6 11

15