问题 1976. -- 做作业

1976: 做作业

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 4
[提交][状态][讨论版]

题目描述

暑假到了,王老师总共布置了n道数学题,题目编号分别为1..n。每道题的难易程序不一样,所以完成每道题所花的时间也不一样,完成第i题要花a[i]分钟。由于小明还要准备出去旅行,所以不能成天做题。他决定只用不超过t分钟时间来做这些数学题,因此必然有的题会空着不做(每道题要么做完,要么不做,不能只做一半)。显然这样会引起王老师的愤怒。如果连续的空题段越长,王老师就越愤怒,一个空题段的长度就是连续的一段没做的题目数。王老师发怒的程度(简称发怒度)等于最长的空题段长度,现在,小明想知道他在这t分钟内完成哪些题,才能够尽量降低王老师的发怒度。请编程计算出王老师的最小发怒度的数值(不需输出方案)。

输入

第一行为两个整数n,t,代表共有n道题目,t分钟时间。
以下一行,为n个整数,依次为a[1], a[2],... a[n],意义如上所述。

输出

仅一行,一个整数w,为最低的发怒度。

样例输入

17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

样例输出

3

提示

60%数据 n<=2000

100%数据 0<n<=50000,0<a[i]<=3000,0<t<=100000000

来源

[提交][状态]