Byteotia 的国王 Byteasar III the Bold 正在计划突袭敌人的城堡。城堡的三面被无法逾越的护城河环绕，Byteasar 别无选择，只能从第四面围攻城堡。然而，这一侧并非完全没有防御：皇家侦察兵报告说，沿着这面墙有许多深坑（trous de loup）。Byteasar 希望攻击墙上尽可能长的一段连续区域。为此，他必须清除掉其中的一些深坑。英明的国王决定用沙袋填平其中一些深坑，并用一块大木板（Great Plank）覆盖另一些深坑。

沿着墙壁共有 $n$ 个深坑。Byteasar 的军队拥有 $p$ 个沙袋。填平第 $i$ 个深坑需要 $w_i$ 个沙袋。此外，大木板最多可以覆盖 $d$ 个连续的深坑。

请帮助 Byteasar 确定，如果他的军队能够最优地利用资源（即沙袋和大木板），他们可以攻击的墙壁最长连续段是多少。换句话说，确定可以被清除的连续深坑的最大数量。

输入格式

标准输入的第一行包含三个整数 $n, p$ 和 $d$ ($1 \le d \le n \le 2\,000\,000, 0 \le p \le 10^{16}$)，分别表示深坑的数量、沙袋的数量以及大木板的覆盖长度，整数之间由空格分隔。

接下来的行描述了深坑：包含一个由 $n$ 个整数组成的序列 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$)，整数之间由空格分隔；$w_i$ 表示填平第 $i$ 个深坑所需的沙袋数量。

在总分占比 30% 的测试点中，满足额外条件 $n \le 3000$。

输出格式

标准输出仅包含一行，即一个整数：Byteasar 的军队可以攻击的墙壁最长连续段的长度。

样例

输入 1

9 7 2
3 4 1 9 4 1 7 1 3

输出 1

5

说明

第 2、3 和 6 号深坑可以用沙袋填平（消耗了 7 个可用沙袋中的 6 个），而第 4 和 5 号深坑可以用大木板覆盖。这样，五个连续的深坑（第 2 到 6 号）就被清除了。

样例测试说明

1. $n = 100, p = 49, d = 50$，所有 $w_i = 1$；除一个深坑外，其余所有深坑均可被清除。
2. $n = 500\,000, p = 1, d = 1000$，偶数编号的深坑需要两个沙袋，而奇数编号的深坑仅需一个。