#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Split Largest Sum - Classic Problems | Repovive

CLS57. Split Largest Sum

2s256 MB

Split an array into at most $k$ non-empty consecutive parts. Minimize the largest part sum.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le a_i \le 10^9$

Input

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

Output

sum_{\min}

Samples

Input

5 2
7 2 5 10 8

Explanation

Splitting as 7 2 5 and 10 8 makes the largest part sum 18, which is optimal.

Output

Input

4 4
1 2 3 4

Explanation

Each element can be its own part, so the largest part sum is the maximum element, 4.

Output

Input

6 3
5 1 2 7 3 4

Explanation

One optimal split is 5 1 2, 7, and 3 4, giving largest sum 8.

Output

Split an array into at most $k$ non-empty consecutive parts. Minimize the largest part sum.

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le a_i \le 10^9$

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

sum_{\min}