Description

Given a sequence of length $n$, you have one chance to choose a contiguous segment of length at most $d$ and change all numbers inside it to $0$. Find the longest contiguous segment such that the sum of all numbers within this segment does not exceed $p$.

Input Format

The first line contains three integers, $n, p, d$.

The second line contains $n$ integers; the $i$-th integer is $w_i$, the $i$-th number in the sequence.

Output Format

Output a single integer, the length of the longest valid segment after the modification.

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

5

Hint

Constraints

For $100\%$ of the testdata, $1 \le d \le n \le 2 \times 10^6$, $0 \le p \le 10^{16}$, $1 \leq w_i \leq 10^9$.

Original title: Wilcze doły.

Translated by ChatGPT 5