您负责的工地在一条街道上挖了 n 个洞（均匀分布，编号从 1 到 n）。您希望重新开放街道上尽可能长的连续部分。因此，您需要填平缺口处所有对外开放的洞。

要填满第 i 个洞，需要 w_i 千克混凝土（0 <= w_i <= 10^9）。你手头有 p 千克混凝土（0 <= p <= 10^9）。你还有一块长度为 d 的木板，它可以覆盖 d 个连续的孔。

请计算你能填充或覆盖的最大连续孔洞数。

输入： 输入的第一行包含三个整数：n、p 和 d。 第二行包含 n 个整数：w_1, w_2 ..., w_n。 输出： 显示可填充或覆盖的最大连续孔洞数。

subtasks:

在所有测试中，1 <= d <= n。

子任务 1（20 分）：n <= 10^2。

子任务 2（30 分）：n <= 10^3。

子任务 3（40 分）：n <= 10^5。

子任务 4（10 分）：n <= 10^6。

示例

输入:

9 7 2

3 4 1 9 4 1 7 1 3

输出:

5

您可以用混凝土填满 2、3 和 6 号孔，用长度为 2 的木板盖住 4 和 5 号孔。