Reference: LeetCode 1642 — Furthest Building You Can Reach

There are ~n~ buildings numbered from ~0~ to ~n-1~. Their heights are given by the array heights.

You begin at building ~0~ and attempt to move from building ~i~ to building ~i+1~.

• If ~heights[i+1] \le heights[i]~, the move requires no resources.
• Otherwise, you must either use one ladder or spend ~heights[i+1] - heights[i]~ bricks.
• A ladder can cover a climb of any height.
• Each ladder may be used only once.

Given the number of available bricks and ladders, determine the index of the furthest building you can reach.

Input

• The first line contains three integers: ~n~, ~bricks~, and ~ladders~.
• The second line contains ~n~ integers: ~heights_0, heights_1, \ldots, heights_{n-1}~.

Output

• Print one integer: the index of the furthest reachable building.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le heights_i \le 10^6~
• ~0 \le bricks \le 10^9~
• ~0 \le ladders \le n~

Example 1

Input:

7 5 1
4 2 7 6 9 14 12

Output:

4