题目描述

给定 $N$ 个整数组成一个序列 $A_1,A_2,\cdots, A_N$，请设计一种划分方法，能将它们分割成 $M$ 段（每段都应该是连续的），且各片段数字之和的最大值达到最小，输出这个最小值。

输入格式

• 第一行：两个整数 $N$ 与 $M$；
• 第二行：$N$ 个整数 $A_1,A_2,\cdots, A_N$。

输出格式

• 单个整数：表示最大段之和的最小值

样例输入

4 2
10 20 30 40

样例输出

60

样例解释

10 20 30 | 40

数据范围

• 对于 $30\%$ 的数据 $1\leq n\leq 100$；
• 对于 $60\%$ 的数据 $1\leq n\leq 5000$；
• 对于 $100\%$ 的数据 $1\leq n\leq 200,000$；
• $1\leq a_i\leq 10000$，$1\leq m\leq n$。