Furthest Ascent Index

You are given an integer array heights, an integer units, and an integer skips. You start at index 0 and move to consecutive indices 1, 2, ....

Moving from index i to i + 1:

• if heights[i + 1] <= heights[i], the move is free;
• otherwise the move is an ascent of heights[i + 1] - heights[i]. You must either spend that many units from your budget, or spend one of your skips (a skip covers any single ascent completely).

Return the furthest index you can reach using the budget and skips optimally.

Examples

Example 1

Input: heights = [4, 2, 7, 6, 9, 14, 12], units = 5, skips = 1
Output: 4
Explanation: Ascents are 2->7 (5), 6->9 (3), 9->14 (5). Spend 5 units on the
first, the skip on the second. The third ascent cannot be covered, so index 4
is the furthest reachable.

Example 2

Input: heights = [4, 12, 2, 7, 3, 18, 20, 3, 19], units = 10, skips = 2
Output: 7

Example 3

Input: heights = [14, 3, 19, 3], units = 17, skips = 0
Output: 3
Explanation: The single ascent 3->19 costs 16 units.