最长稳定训练段(segment)

题目描述

DAMON THRONE\text{DAMON THRONE} 的训练系统记录了 nn 天的训练强度。

ii 天的训练强度为 aia_i

如果连续若干天的训练强度总和不超过 KK,则称这段训练是 稳定训练段

现在请你求出:

  1. 最长稳定训练段的长度;
  2. 在长度最长的所有稳定训练段中,训练强度总和最大是多少。

输入格式

第一行包含两个整数 n,Kn,K,表示训练天数和稳定训练段允许的最大强度总和。

第二行包含 nn 个整数:a1,a2,,ana_1,a_2,\ldots,a_n,表示每天的训练强度。

输出格式

输出一行两个整数,分别表示:

  • 最长稳定训练段的长度;
  • 在最长长度下,训练强度总和的最大值。

如果不存在任何稳定训练段,输出:

0 0

输入输出样例 #1

输入 #1

8 10
2 3 5 4 1 6 2 2

输出 #1

3 10

样例解释 #1

长度为 33 的稳定训练段有:

2,3,52,3,5

总和为:

1010

也有:

4,1,64,1,6

总和为:

1111

11>1011 > 10,不稳定。

还有:

6,2,26,2,2

总和为:

1010

因此最长稳定训练段长度为 33,在长度为 33 的稳定训练段中最大总和为 1010

输入输出样例 #2

输入 #2

5 3
4 5 6 7 8

输出 #2

0 0

数据范围与约定

对于所有测试数据,保证:

$$1 \le n \le 2\times 10^5,\quad 1 \le K \le 10^{14},\quad 1 \le a_i \le 10^9 $$
测试点 分值 nn ai,Ka_i,K 特殊性质
121\sim 2 1010 100\le 100 1000\le 1000
343\sim 4 2020 2000\le 2000 109\le 10^9
565\sim 6 105\le 10^5 1014\le 10^{14} A\text{A}
787\sim 8 B\text{B}
9109\sim 10 3030 2×105\le 2\times 10^5

特殊性质 A\text{A}:保证所有 aia_i 相等。

特殊性质 B\text{B}:保证存在至少一个稳定训练段。