Subsegments with Small Sums

时间限制：2s
空间限制：1024MB

题目描述

给定正整数 $S$。对于一个正整数序列 $x$，把它划分成若干个连续段，并要求每段的元素和都不超过 $S$。满足要求的划分中，连续段数量的最小值记为 $f(x)$。

现在给定长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$，求

$$\sum_{1\le l\le r\le N} f((A_l,A_{l+1},\ldots,A_r)).$$

输入格式

第一行输入两个整数 $N,S$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出所求的和。

样例输入 1

3 3
1 2 3

样例输出 1

8

样例输入 2

5 1
1 1 1 1 1

样例输出 2

35

样例输入 3

5 15
5 4 3 2 1

样例输出 3

15

样例输入 4

20 1625597454
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

样例输出 4

588

数据范围

对于所有数据，$1\le N\le250000$，$1\le S\le10^{15}$，$1\le A_i\le\min(S,10^9)$。

子任务编号	分值	特殊限制
1	10	$\sum A_i\le S$
2		所有 $A_i=S$
3	20	$N\le40$
4	30	$N\le5000$
5		无特殊限制