#515. 哦耶,爽爽的剧

哦耶,爽爽的剧

题目背景

鱼小龙准备坐长途车,担心途中网络不好,想提前缓存几集电视剧。他希望在有限的流量预算内,缓存尽可能多的连续剧集。

题目描述

这部电视剧共有 nn 集,按播放顺序编号为 11 到 nn。

部分剧集已经缓存。将第 ii 集缓存完整,还需要下载 aia_i MB 的数据;如果 ai=0a_i=0,表示这一集已经缓存完整。

鱼小龙最多还能下载 BB MB 的数据。他可以选择任意一段编号连续的剧集,将这段中的每一集都缓存完整。所需下载量为这段剧集对应的 aia_i 之和,不能超过 BB。

求鱼小龙最多能选择多少集。如果没有任何一集能够在预算内缓存完整,则输出 00。

输入格式

第一行包含两个整数 nn 和 BB,分别表示剧集数量和剩余流量预算。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示每一集还需要下载的数据量。

输出格式

输出一个整数,表示最多能选择的连续剧集数量。

样例

8 6
2 0 3 1 0 4 2 0
5
5 0
0 2 0 0 3
2

样例说明

样例 1 中,可以选择第 11 集到第 55 集,还需要下载 2+0+3+1+0=62+0+3+1+0=6 MB 的数据。不存在长度超过 55 且下载量不超过 66 MB 的连续剧集,因此答案为 55。

样例 2 中,鱼小龙没有剩余流量,但第 33、第 44 集都已经缓存完整,可以直接选择这两集,因此答案为 22。

数据范围

  • 1≤n≤2×1051\le n\le 2\times10^5;
  • 0≤B≤10140\le B\le 10^{14};
  • 0≤ai≤1090\le a_i\le 10^9。

时间限制: 22 秒。
内存限制: 256256 MB。