题目描述

马上就要放暑假啦！

为了激励一下公司的员工，徐老师决定给所有人发奖金！

发奖金的方式非常简单，徐老师会在桌上一字排开 $n$ 张纸团，每张纸团上会写着一个数字 $a_i$，为了平衡公司成本，这里的数字可能会存在负数

游戏规则是：每人只能抓一次，只能抓取一段连续的纸团，所有纸团上的数字和就是这次可以获得的奖金，如果有人不幸获得了负数的奖金，那么就意味着他要被扣掉对应的工资，所以徐老师也允许大家选择不抓纸团，那么奖金就是 $0$ 元

现在石老师是第一个抽奖金的人，石老师想知道，他一共有多少种不同的方案可以获得至少 $k$ 元的奖金？

输入格式

输入第一行包含一个整数 $n,k$ 含义如题

输入第二行包含 $n$ 个整数，$a_i$ 依次表示每个纸团上的数字

输出格式

输出一个整数表示有多少种不同的方案

数据范围

对于 $30\%$ 的数据：$1 ≤ n ≤ 2000，-10^8 ≤ k ≤ 10^8，-10^4≤ a_i ≤ 10^4$。

对于另外 $10\%$ 的数据： $a_i < 0, k = 0$

对于 $100\%$ 的数据：$1≤ n ≤ 3* 10^5$，$-10^{18}≤ k ≤ 10^{18}，-10^9≤ a_i≤ 10^9$。

样例输入1

4 1
-5 4 3 -3

样例输出1

5

样例解释1

五种方案分别为 $[-5,4,3],[4],[4,3],[4,3,-3],[3]$

样例输入2

10 -1
-5 4 5 -4 1 3 5 8 -4 5

样例输出2

52

样例输入3

5 0
-1 -1 -1 -1 -1

样例输出3

1