Demonstration

题意翻译

原题面zz敏感内容已替换。 ## 题目描述 有一些FD派认为对国王的选举不公平，他们希望申请一个广场以组织活动。 该国首都共有 $n$ 个广场，按离市中心的距离递增顺序依次编号 $1$ 到 $n$，FD派希望活动离市中心越近越好。 ZF希望对他们的活动进行一些阻挠。距离活动举行还有 $k$ 天（保证 $k<n$），在这 $k$ 天内，ZF都会对申请进行审批。每次审批都将经过以下步骤： - FD派申请在某没有组织活动的广场举行活动。（最开始所有的广场都是空闲的。） - ZF尝试在该广场花费一定代价举行活动，使得该广场不再空闲，然后驳回申请并提议将反对派的活动转移到 $n$ 号广场。**如果FD派申请了第 $n$ 号广场，ZF会直接同意该申请，而不选择组织活动。**如果ZF没有足够的资金组织活动，那么FD派的申请将被同意。（如果申请被同意了，该广场还是空闲的。） - 无论申请被驳回还是同意，只要活动时间没到，FD派都可以选择在第二天继续提交一份申请。 ZF在第 $i$ 个广场举行活动的花费是 $a_i$。由于一些原因，ZF只有 $b$ 的资金，问FD派可以申请的所有广场中编号最小的是哪个？ 注意：ZF的行动始终取决于FD派的行动。 ## 输入格式 第一行包含两个整数 $n$ 和 $k$，分别表示广场数和距离活动举行的天数。 第二行包含一个整数 $b$，表示ZF拥有的资金。 第三行包含 $n$ 个整数 $a_i$，表示ZF在每个广场举行活动的花费。 ## 输出格式 一行一个整数，表示FD派可以申请到的广场的最小编号。 ## 数据范围 $1 \leq k < n \leq 10^5$, $1 \leq b \leq 10^{18}$, $1 \leq a_i \leq 10^9$。

题目描述

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&lt;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: - The opposition shall apply to hold a demonstration at a free square (the one which isn't used by the administration). - The administration tries to move the demonstration to the worst free square left. To do this, the administration organizes some long-term activities on the square, which is specified in the application of opposition. In other words, the administration starts using the square and it is no longer free. Then the administration proposes to move the opposition demonstration to the worst free square. If the opposition has applied for the worst free square then request is accepted and administration doesn't spend money. If the administration does not have enough money to organize an event on the square in question, the opposition's application is accepted. If administration doesn't have enough money to organize activity, then rest of administration's money spends and application is accepted - If the application is not accepted, then the opposition can agree to the administration's proposal (that is, take the worst free square), or withdraw the current application and submit another one the next day. If there are no more days left before the meeting, the opposition has no choice but to agree to the proposal of City Hall. If application is accepted opposition can reject it. It means than opposition still can submit more applications later, but square remains free. In order to organize an event on the square $ i $ , the administration needs to spend $ a_{i} $ 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&lt;n<=10^{5} $ ). The second line contains a single integer $ b $ — the number of bourles the administration has ( $ 1<=b<=10^{18} $ ). The third line contains $ n $ space-separated integers $ a_{i} $ — the sum of money, needed to organise an event on square $ i $ ( $ 1<=a_{i}<=10^{9} $ ). 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.

输入输出样例

输入样例 #1

5 2
8
2 4 5 3 1

输出样例 #1

2

输入样例 #2

5 2
8
3 2 4 1 5

输出样例 #2

5

输入样例 #3

5 4
1000000000000000
5 4 3 2 1

输出样例 #3

5

说明

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.

题意翻译

原题面zz敏感内容已替换。 ## 题目描述 有一些FD派认为对国王的选举不公平，他们希望申请一个广场以组织活动。 该国首都共有 $n$ 个广场，按离市中心的距离递增顺序依次编号 $1$ 到 $n$，FD派希望活动离市中心越近越好。 ZF希望对他们的活动进行一些阻挠。距离活动举行还有 $k$ 天（保证 $k<n$），在这 $k$ 天内，ZF都会对申请进行审批。每次审批都将经过以下步骤： - FD派申请在某没有组织活动的广场举行活动。（最开始所有的广场都是空闲的。） - ZF尝试在该广场花费一定代价举行活动，使得该广场不再空闲，然后驳回申请并提议将反对派的活动转移到 $n$ 号广场。**如果FD派申请了第 $n$ 号广场，ZF会直接同意该申请，而不选择组织活动。**如果ZF没有足够的资金组织活动，那么FD派的申请将被同意。（如果申请被同意了，该广场还是空闲的。） - 无论申请被驳回还是同意，只要活动时间没到，FD派都可以选择在第二天继续提交一份申请。 ZF在第 $i$ 个广场举行活动的花费是 $a_i$。由于一些原因，ZF只有 $b$ 的资金，问FD派可以申请的所有广场中编号最小的是哪个？ 注意：ZF的行动始终取决于FD派的行动。 ## 输入格式 第一行包含两个整数 $n$ 和 $k$，分别表示广场数和距离活动举行的天数。 第二行包含一个整数 $b$，表示ZF拥有的资金。 第三行包含 $n$ 个整数 $a_i$，表示ZF在每个广场举行活动的花费。 ## 输出格式 一行一个整数，表示FD派可以申请到的广场的最小编号。 ## 数据范围 $1 \leq k < n \leq 10^5$, $1 \leq b \leq 10^{18}$, $1 \leq a_i \leq 10^9$。