#CF279B. 书

书

CF279B Books

题目描述

\hspace{15pt}你有 nn 本书,阅读第 ii 本书需要花费 aia_i 分钟,而你现在一共有 mm 分钟。

\hspace{15pt}你读书的方式如下:

∙ \hspace{23pt}\bullet\,找出任意一个整数 x(1≦x≦n)x \left(1 \leqq x \leqq n\right),并按编号从小到大的顺序阅读第 x∼nx \sim n 本书;

∙ \hspace{23pt}\bullet\,如果你读完了第 nn 本书,那么读书结束;

∙ \hspace{23pt}\bullet\,如果你准备阅读第 ii 本书,但是剩下的时间小于 aia_i(也就是读不完这本书),那么你不可以开始读这本书,并且读书结束。

\hspace{15pt}换句话说,如果你开始读一本书,就必须要读完,否则就不能读。

\hspace{15pt}请求出最多能读多少本书。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq 10^9\right)$,分别代表书的数量和限定时间。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^4\right)$,代表阅读每本书所耗费的时间。

输出格式

\hspace{15pt}在一行上输出一个整数,代表最多能读的书的数量。

测试样例

4 5
3 1 2 1

3

3 3
2 2 3

1