题目描述

给定 $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

样例解释 1

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$。