最小m段和问题

题目描述

给定一个由 n 个整数 a_1, a_2, \dots, a_n 组成的序列，现在需要将这个序列分割成 m 段，每段必须是原序列中连续的一部分。如何分割才能使这 m 段子序列的和的最大值达到最小？输出这个最小的最大值。

例如，序列为 5 4 3 2 1， n=5 ， m=3 ，可以分割为 5 | 4 | 3 2 1，各段和分别为 5、4、6，最大值为 6，这是所有分割方案中最大值最小的，因此输出 6。

输入

• 第一行包含两个整数 n 和 m ，用空格隔开。
• 第二行包含 n 个整数 a_1, a_2, \dots, a_n ，表示原序列。

输出

输出一个整数，表示最小的最大段和。

样例

提示

数据范围与约定

• 1 \le n \le 5000
• 1 \le m \le 100 ，且 m \le n
• 0 \le a_i \le 100