Array Division

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array of $n$ positive integers, divide it into exactly $k$ non-empty contiguous subarrays covering the whole array. If the sum of subarray $j$ is $S_j$, minimize

Input

The first line contains $n,k$. The second line contains $x_1,\ldots,x_n$.

Output

Print the minimum possible value of the maximum subarray sum.

Subtasks

• Subtask 1 — 20%: $k=1$ or $k=n$.
• Subtask 2 — 30%: $1\le n\le2000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le k\le n$, $1\le x_i\le10^9$.

Examples

Input

5 3
2 4 7 3 5

Output

8

Explanation

An optimal division is $[2,4],[7],[3,5]$, whose maximum sum is $8$.