描述

给定一个长度为 $N$ 的正整数序列，将序列分成 $M$ 段，使得每段的和的最大值最小。

格式

输入

• 第一行包含两个整数 $N$ 和 $M$ ($1 \leq M \leq N \leq 10^6$)。
• 第二行包含 $N$ 个整数 $A[1], A[2], \dots, A[N]$ ($1 \leq A[i] \leq 1000$)。

输出

• 输出一个整数：每段和的最大值的最小值。

样例

输入1

5 2
9 1 2 4 5

输出1

11

限制

• 时间限制：1s