Fill the Containers

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ vessels in a fixed conveyor-belt order, and vessel $i$ contains $c_i$ units of milk. All milk from one vessel must be poured into exactly one container; a vessel may not be split between containers.

Number the $m$ containers from $1$ to $m$. The vessel order must be preserved: if vessel $i$ comes before vessel $j$, and they are poured into containers $r$ and $s$, respectively, then

Thus, the vessels assigned to each used container form a contiguous segment of the original sequence. Some containers may remain unused.

The containers do not have to have the same capacity. Each container may be assigned its own capacity. Minimize the largest capacity among the used containers. Equivalently, find the smallest $C$ such that all milk can be transferred in order using at most $m$ containers and the total milk poured into every used container is at most $C$.

Input

The first line contains $n,m$. The second line contains $c_1,\ldots,c_n$.

Output

Print the minimum possible value of the maximum container capacity.

Subtasks

• Subtask 1 — 20%: $m=1$ or $m\ge n$.
• Subtask 2 — 30%: $1\le n\le100$.
• Subtask 3 — 50%: $1\le n\le1000$, $1\le m\le10^6$, $1\le c_i\le10^6$.

Examples

Input

5 3
1 2 3 4 5

Output

6

Explanation

The groups $[1,2,3]$, $[4]$, and $[5]$ require maximum capacity $6$, which is optimal.