5.出题方案

题目描述

现在小泽的手上有$n$道难题，编号分别为$1 \sim n$，第$i$道题的难度系数是$a_i$。小泽想用这些题出比赛，他会把题目按照编号划分为若干个非空连续区间，每个区间对应了一场比赛。

特别的，如果某场比赛的题目难度系数之和超过了给定的常数$m$，这场比赛会过于毒瘤，所以他不希望出现这样的情况。

定义每场比赛的难度系数为这场比赛所有题目难度系数的最大值。

小泽想让你找出一组合法方案，使得所有比赛的难度系数之和最小。

输入格式

第一行两个整数$n$，$m$。

接下来$n$行，每行一个整数$a_i$。

输出格式

一行一个整数，表示最小的难度系数之和。

数据范围与提示

• 对于$40\%$的数据，$n \leq 1000$；
• 对于$100\%$的数据，$1 \leq n \leq 3 \times 10^{5}$，$1 \leq a_i \leq 10^{6}$，$1 \leq m \leq 1.1 \times 10^{9}$。

样例

8 17
2
2
2
8
1
8
2
1

12

说明

可以划分为$[1,3]$，$[4,6]$，$[7,8]$，难度系数为$2 + 8 + 2 = 12$。