题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Wilcze doły

字节城国王 Bajtazar III 雄心勃勃，计划攻打敌方城堡。城堡三面环绕难以逾越的护城河，Bajtazar 只能从第四面城墙发起进攻。然而，敌人在城墙外挖了 $n$ 个深不可测的狼坑来阻碍进攻。Bajtazar 希望攻击尽可能长的连续城墙段，为此需填平部分狼坑。他决定用沙袋填埋一些坑，用巨型木板覆盖另一些坑。

城墙外有 $n$ 个狼坑，Bajtazar 拥有 $p$ 袋沙子，填埋第 $i$ 个坑需 $w_i$ 袋沙子。巨型木板可覆盖 $d$ 个连续的坑。请你帮助 Bajtazar 计算通过最佳利用沙袋和木板，他能填平的最长连续狼坑段的长度。

输入格式

第一行包含三个整数 $n, p, d$ $(1 \leq d \leq n \leq 2000000, 0 \leq p \leq 10^{16})$，分别表示狼坑数量、沙袋数量和巨型木板可覆盖的连续坑数。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$ $(1 \leq w_i \leq 10^9)$，$w_i$ 表示填埋第 $i$ 个狼坑所需的沙袋数。

输出格式

输出一行，一个整数，表示 Bajtazar 可攻击的最长连续城墙段的狼坑数。

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

5

Bajtazar 可填埋第 $2$、$3$、$6$ 个坑（使用 $4+1+1=6$ 袋沙子，$7$ 袋中剩余 $1$ 袋），用巨型木板覆盖第 $4$、$5$ 个坑（$d=2$）。这样，他填平第 $2$ 到 $6$ 的 $5$ 个连续坑。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 3000$。