CF191B Demonstration

在贝兰国的首都伯特城，由于国王的最近选举结果，市民们展开了抗议活动。奥瓦尔尼先生领导的反对派认为，此次选举不够公正，他们希望在某个广场上组织一次示威。 伯特城一共有 $n$ 个广场，从 $1$ 到 $n$ 编号。编号越小，离市中心越近。也就是说，广场 $1$ 是最靠近市中心的，而广场 $n$ 最远。自然地，反对派希望尽可能在最接近市中心的广场上举行集会。 距离示威活动还有 $k$ 天（$k < n$）。目前所有广场都是空闲的。不过，城里的市政府并不闲着，批准示威申请的过程可能会变得非常繁复冗长。申请审批的过程将持续几天，具体程序如下： - 反对派每天必须申请一个空闲的广场来举行示威（即没有被市政府占用的广场）。 - 市政府会试图让他们在余下的空闲广场中，选择最不理想的一个进行示威。市政府会在反对派申请的广场上安排长期活动，使之不再空闲。然后建议反对派搬到最不理想的那个空闲广场。如果反对派申请的正好是最不理想的空闲广场，那请求就会被接受，市政府也不会花钱。如果市政府没足够的钱在申请的广场上组织活动，则反对派的申请会被直接通过。如果市政府钱不够用，他们会把剩下的钱用光，但还是得接受申请。 - 如果申请未被接受，反对派能选择同意市政府的建议（使用最不理想的空闲广场），或撤回申请，等到第二天重提。如果剩下的天数不够，反对派就只能接受市政府的建议。如果申请被接受，反对派可以选择拒绝，这意味着他们还是可以在之后继续申请，广场也会保持空闲。 在广场 $i$ 上举办活动需要花费 $a_i$ 布勒。由于经济不景气，市政府只有 $b$ 布勒来阻止反对派。那么，反对派能够选择的最优广场的最小编号是多少？注意，市政府的对策完全取决于反对派的行为。

第一行包含两个整数 $n$ 和 $k$ —— 分别表示广场的数量和示威前剩余的天数（$1 \leq k < n \leq 10^5$）。 第二行包含一个整数 $b$ —— 市政府拥有的布勒数量（$1 \leq b \leq 10^{18}$）。 第三行包含 $n$ 个空格分隔开的整数 $a_i$ —— 在广场 $i$ 上组织活动所需的费用（$1 \leq a_i \leq 10^9$）。

输出一个整数，表示反对派可以顺利组织示威的最小编号的广场。

在第一个示例中，反对派可以先申请广场 3，让市政府在那里举办活动，这样市政府剩下 3 布勒。第二天如果反对派申请广场 2，市政府将无力干扰。 在第二个示例中，反对派只能选择最后一个广场。如果他们一开始就占据前四个广场的任何一个，市政府至少会剩余 4 布勒，这样下一天可以将反对派从任何一个广场赶到最后一个广场。 在第三个示例中，市政府有充足的资金，因此反对派只能占据最后一个广场。 **本翻译由 AI 自动生成**