盾与战锤

题号：NC228138
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

敌人出现了，敌人的技能是获得一个能抵挡一定伤害的护盾。

你有一个长度为 $n$ 的攻击序列，每个攻击都会造成一定伤害，你可以选出它的一个 子序列 进行攻击，每一秒按照子序列中的顺序进行一次攻击。

敌人开始时拥有一个可以抵抗 $s$ 点伤害的护盾，并且它在获得护盾之后第一次被攻击时开始， $k$ 秒之后恢复它的护盾（ $k$ 秒后先恢复护盾再被攻击）。

但是因为 QuantAsk 忘记了敌人刷盾的时间，所以你要对于 $k\in[1,n]$ 求出最大能对敌人造成的伤害。

第一行输入两个正整数 $n,s$ $(1\leq n\leq 10^6,1\leq s\leq 10^9)$ 表示攻击序列长度和敌人护盾能抵抗的伤害。

接下来一行 $n$ 个正整数 $a_i$ $(1\leq a_i\leq 10^{12})$ 表示攻击序列。

输出  行，每行包括一个整数，第  行表示当  时能够造成的最大伤害。

示例1

复制

4 5
5 2 4 1

复制

如当 k=2 时选择 {5,4,1} 或者 {5,4} 均可以造成 4 点伤害。