Longest Subarray with Sum Constraint after Modification

Given a sequence of length \(n\) and an integer \(p\), you are allowed to pick one contiguous segment of length at most \(d\) and change all its elements to \(0\). Your task is to determine the length of the longest contiguous subarray (segment) such that after applying the modification optimally the sum of the subarray is at most \(p\). You may choose not to use the modification if it is not necessary.

Note: In each subarray you consider, you can remove (i.e. set to zero) any contiguous block of at most \(d\) numbers. For a subarray spanning indices \(i\) to \(j\), let its total sum be \(S = \sum_{k=i}^{j} a_k\). If \(L = j-i+1 \le d\), you can remove the entire subarray so that the remaining sum is \(0\). Otherwise, you should remove a contiguous block of exactly \(d\) (or fewer, if advantageous) that maximizes the reduction, making the remaining sum \(S - \max\{\text{sum of any contiguous block of length } \ell,\, 1 \le \ell \le d\}\). The goal is to achieve a remaining sum \(\le p\).

Input Format:

• The first line contains three space-separated integers: \(n\) (the number of elements), \(p\) (the maximum allowed sum) and \(d\) (the maximum length of the segment that can be modified).
• The second line contains \(n\) space-separated integers representing the sequence.

Output Format:

• Output a single integer representing the maximum length of a contiguous subarray that can have a sum less than or equal to \(p\) after applying the modification optimally.

inputFormat

The input consists of two lines:

• The first line contains three space-separated integers \(n\), \(p\), and \(d\).
• The second line contains \(n\) space-separated integers denoting the elements of the sequence.

outputFormat

Output a single integer denoting the length of the longest contiguous subarray that satisfies the sum constraint after optimally setting one contiguous block (of length at most \(d\)) to zero.

sample

5 5 2
1 2 3 2 1

5