6115 - 202602 SACCC:六级第四题 划分（split)

2036 年,第十届 SACCC 认证的考场上,作为选手的苏智打开了第一题。这个题的样例有 n 组数据,数据从 1∼ n 编号, i 号数据的规模为 a i 。 苏智对该题设计出了一个解决方案:将所有数据划分成若干个数据段,段内数据编号连续,接着将同一段内的数据合并成新数据,其规模等于段内原数据的规模最大值。但苏智很快发现由于时空限制,每个数据段的规模和都不能超过 m 。苏智希望生成的新数据的规模和尽可能小。

第一行两个整数 n, m 。 第二行 n 个整数 a i 。

一个整数,表示每一部分最大值的和的最小值

样例1解释:1|3 3|1,此时新数据规模和最小为1+3+1=5

对于 20% 的数据, 1 ≤ n ≤ 10 对于 40% 的数据, 1 ≤ n ≤ 10^3 对于 100% 的数据, 1≤ n ≤ 10^5 , 0 ≤ a i ≤ m ≤ 10^9 。