SP2127 RAIN3 - Rain

琼斯博士是著名的考古学家。他最近在提里巴基群岛进行了一项研究，发现了一个名为气象仪的神奇机器。它曾被提里巴基的最高祭司用来预测天气。这个气象仪上有一个黄色按钮，从创世之初就被神设立。当地人每天都会按下这个按钮，气象仪便会输出一个数字，这个数字代表对第二天降雨量（以毫米为单位）的预测。更确切地说，当按钮被按下第 _i_ 次时（从创世之初开始计数），气象仪会给出第 _i_ 天的预期降雨量。 然而，这个气象仪已经有上千年未被使用，现在没有人知道如何将时间推进到当天。研究者们投入了大量精力研究气象仪的工作机制，提出了一个数学模型：气象仪用一对整数 s\[0\] 和 t\[0\] 初始化。在第 _i_ 步时，气象仪计算： ``` s[i] = (78901 + 31 * s[i-1]) mod 699037 t[i] = (23456 + 64 * t[i-1]) mod 2097151 ``` 然后，第 _i_ 步的输出将是： ``` a[i] = (s[i] mod 100 + 1) * (t[i] mod 100 + 1) ``` 琼斯博士的朋友琳达·沃森计划去提里巴基群岛度假。她想在那里尽可能久地停留，但她不能忍受过多的降雨。在整个假期中，她最多可以忍受 M 毫米的降雨量。为了帮助琳达，琼斯博士希望计算她能在提里巴基群岛安全停留的最长天数。他对气象仪进行了 N 次模拟，从而获得了一个序列 a\[1\], a\[2\], ..., a\[N\]，这些数代表接下来 N 天的降雨预测。现在琼斯博士想找到最大的 K，确保对于任何长不超过 K 天的时间段（从第 i 天到第 j 天），降雨预测和 a\[i\] + a\[i+1\] + ... + a\[j\] 都不超过 M。这样，琳达可以确定自己在提里巴基停留不超过 K 天是可以承受降雨的。（假设 N 充分大）

多组测试数据。每组数据的第一行包含两个整数 N 和 M，分别表示气象仪的模拟步数和琳达能忍受的最大降雨量。接下来的一行给出 N 个整数 a\[1\], a\[2\], ..., a\[N\]，表示 N 天的降雨预测。

对于每一组测试数据，输出一个整数 K，表示琳达可以安全停留在提里巴基的最长天数。

$$ 1 \leq N \leq 10^5, \quad 1 \leq M \leq 10^9, \quad 1 \leq a[i] \leq 100 $$ **本翻译由 AI 自动生成**