|Codeforces Round #121 (Div. 1)|
In the capital city of Berland, Bertown, demonstrations are against the recent election of the King of Berland. Berland opposition, led by Mr. Ovalny, believes that the elections were not fair enough and wants to organize a demonstration at one of the squares.
Bertown has n squares, numbered from 1 to n, they are numbered in the order of increasing distance between them and the city center. That is, square number 1 is central, and square number n is the farthest from the center. Naturally, the opposition wants to hold a meeting as close to the city center as possible (that is, they want an square with the minimum number).
There are exactly k (k < n) days left before the demonstration. Now all squares are free. But the Bertown city administration never sleeps, and the approval of an application for the demonstration threatens to become a very complex process. The process of approval lasts several days, but every day the following procedure takes place:
In order to organize an event on the square i, the administration needs to spend ai bourles. Because of the crisis the administration has only b bourles to confront the opposition. What is the best square that the opposition can take, if the administration will keep trying to occupy the square in question each time? Note that the administration's actions always depend only on the actions of the opposition.
The first line contains two integers n and k — the number of squares and days left before the meeting, correspondingly (1 ≤ k < n ≤ 105).
The second line contains a single integer b — the number of bourles the administration has (1 ≤ b ≤ 1018).
The third line contains n space-separated integers ai — the sum of money, needed to organise an event on square i (1 ≤ ai ≤ 109).
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Print a single number — the minimum number of the square where the opposition can organize the demonstration.
2 4 5 3 1
3 2 4 1 5
5 4 3 2 1
In the first sample the opposition can act like this. On day one it applies for square 3. The administration has to organize an event there and end up with 3 bourles. If on the second day the opposition applies for square 2, the administration won't have the money to intervene.
In the second sample the opposition has only the chance for the last square. If its first move occupies one of the first four squares, the administration is left with at least 4 bourles, which means that next day it can use its next move to move the opposition from any square to the last one.
In the third sample administration has a lot of money, so opposition can occupy only last square.