Maximizing the Minimum Water Level

Little Blue has $n$ bottles arranged from left to right. The $i$-th bottle initially contains $a_i$ units of water. For aesthetic reasons, Little Blue dyes the water in a cyclic fashion using $k$ different colors; that is, the water in the $i$-th bottle and the $(i+k)$-th bottle have the same color.

Little Blue noticed that some bottles have too little water. Hence, he permits the following operation: if two bottles $i$ and $j$ ($i<j$) have the same color, then an arbitrary integer amount of water may be poured from bottle $i$ to bottle $j$.

The task is to determine the maximum possible value of $X=\min\{a_i\}$ that can be achieved after performing an arbitrary number of such operations.

It can be observed that the operations only allow water to be moved forward (from left to right) among bottles of the same color. Consider one color group consisting of bottles with indices $i_1, i_2, \dots, i_m$ (with $i_1 < i_2 < \dots < i_m$). Let $S_r=\sum_{j=1}^{r}a_{i_j}$ be the prefix sum in that group. In order to achieve that every bottle in this group contains at least $X$ units of water, it is necessary and sufficient that for all $r\in\{1,2,\dots,m\}$, the condition

$$S_r \ge rX$$

holds. Therefore, the maximum $X$ attainable for this group is

$$X = \min_{1\le r\le m} \left\lfloor \frac{S_r}{r} \right\rfloor.$$

The answer to the problem is the minimum of such values over all $k$ color groups.

inputFormat

The input is given in the following format:

$n\ k$
$a_1\ a_2\ \dots\ a_n$

where $n$ and $k$ are positive integers, and $a_i$ represents the initial units of water in the $i$-th bottle.

outputFormat

Output a single integer --- the maximum possible value of $\min\{a_i\}$ over all bottles that can be achieved after any number of operations.

sample

5 2
5 3 7 6 2

3