Discounted peak stretch: hints, no solution

A factory buys electricity under a peak-shaving contract. For any period of consecutive hours, the utility waives the j largest hourly readings inside that period and bills the rest. The billed amount of a period is the sum of its readings after removing its j largest ones. A period with j or fewer hours is billed nothing. When several readings share a value, it does not matter which of them is waived.

Given the non-negative hourly readings, a budget and j, return the length of the longest period whose billed amount is at most the budget. The target is about n log n or better; trying every period and sorting each is too slow.

Examples

Input

readings = [4, 9, 2, 7, 1, 3], budget = 5, j = 1

Output

3

Note

The period 2, 7, 1 bills 2 + 1 = 3 after waiving 7, and no period of four hours fits within 5.

Input

readings = [3, 1, 2], budget = 1, j = 0

Output

1

Note

With j = 0 nothing is waived, so this is a plain budget window.

Input

readings = [8, 9], budget = 0, j = 0

Output

0

Note

The budget of 0 only allows periods whose billed part is zero.

Constraints

• 0 <= readings.length <= 40000
• 0 <= readings[i] <= 1000
• 0 <= budget <= 4000000, 0 <= j <= 40000

Hint 1: a nudge

If a period is affordable, is every shorter period inside it affordable too? Try removing one reading at either end.

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing