Copying Books

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

There are $m$ books in fixed order, with $p_i$ pages. Partition them into exactly $k$ non-empty contiguous groups, one per scribe. Minimize the maximum group sum. The PHOJ version asks only for this unique optimal value.

Input

The first line contains $m,k$. The second line contains $p_1,\ldots,p_m$.

Output

Print the minimum possible maximum workload.

Subtasks

• Subtask 1 — 20%: $m\le30$.
• Subtask 2 — 30%: $m\le200$.
• Subtask 3 — 50%: $1\le k\le m\le500$, $1\le p_i<10^7$.

Example

Input

9 3
100 200 300 400 500 600 700 800 900

Output

1700

Explanation

An optimal partition has maximum group sum 1700.