Description

给定一个长度为 $n$ 的序列 $A_i$，现在要求把这个序列分成恰好 $K$ 段，(每一段是一个连续子序列，且每个元素恰好属于一段)，并且每段至少有一个元素，使得和最大的那一段最小。

请你求出这个最小值。

Input Format

第一行两个整数 $n, K$，意义见题目描述。

接下来一行 $n$ 个整数表示序列 $A_i$。

Output Format

仅一行一个整数表示答案。

Sample

样例输入

9 4
1 1 1 3 2 2 1 3 1

样例输出

5

Hint

$20 \%$ 的数据，$n \leq 100$

另有 $20 \%$ 的数据，$A_i \geq 0$

另有 $20 \%$ 的数据，$A_i \leq 0$

另有 $20 \%$ 的数据，$K \leq 10$

$100 \%$ 的数据，$ 1 \leq K \leq n \leq 5 \times 10 ^ 4, |A_i| \leq 3 \times 10 ^ 4 $