在贝尔兰首都贝尔敦,示威活动反对最近举行的贝尔兰国王选举。以奥瓦尔尼先生为首的贝尔兰反对派认为选举不够公平,并希望在其中一个广场组织示威活动。
Bertown有n个广场,编号从1到n,它们按照距市中心距离递增的顺序编号。即,1号方格位于中心,n号方格距离中心最远。反对派自然希望在尽可能靠近市中心的地方举行会议(即他们想要一个人数最少的广场)。
距离演示还剩 k (k < n) 天。现在所有的方块都是空闲的。但伯敦市政府从不休息,示威申请的批准可能会成为一个非常复杂的过程。批准过程持续几天,但每天都会发生以下程序:
- 反对派应申请在自由广场(政府未使用的广场)举行示威。
- 政府试图将示威活动转移到左边最差的自由广场。为此,政府在广场上组织了一些长期活动,这些活动在反对派申请中得到了具体说明。换句话说,政府开始使用该广场,并且不再免费。然后政府提议将反对派示威活动转移到最糟糕的自由广场。如果反对派申请了最差的免费广场,那么请求就会被接受,政府也不会花钱。如果政府没有足够的资金在相关广场上组织活动,反对派的申请就会被接受。如果政府没有足够的资金来组织活动,则政府的其余资金将被花费并接受申请
- 如果申请不被接受,那么反对者可以同意政府的提议(即取最差的自由方),或者撤回当前的申请并在第二天提交另一份申请。如果距离会议只剩下几天了,反对党别无选择,只能同意市政厅的提议。如果申请被接受,反对意见可以拒绝。这意味着反对派仍然可以稍后提交更多申请,但 Square 仍然是免费的。
为了在 i 广场组织一次活动,政府需要花费 ai 布尔斯。由于这场危机,政府只有b布尔斯来对抗反对派。如果政府每次都试图占领有问题的方格,那么反对派可以占据的最佳方格是什么?请注意,政府的行动始终仅取决于反对派的行动。
输入
第一行包含两个整数 n 和 k — 会议前剩余的格数和天数,相应地 (1 ≤ k < n ≤ 105)。
第二行包含一个整数 b — 政府拥有的布尔数 (1 ≤ b ≤ 1018)。
第三行包含 n 个空格分隔的整数 ai — 在 i 方格上组织活动所需的资金总额 (1 ≤ ai ≤ 109)。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
打印一个数字——反对派可以组织示威的最小广场数量。
示例
输入 #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
注意
在第一个示例中,反对派可以这样做。第一天,它适用于方格 3。管理部门必须在那里组织一场活动,最终获得 3 个布尔。如果第二天反对派申请第 2 方,政府将没有资金进行干预。
在第二个样本中,对手只有最后一个方格的机会。如果它的第一步占据了前四个方格中的一个,那么政府就剩下至少 4 个方块,这意味着第二天它可以使用下一步行动将反对派从任何一个方格移动到最后一个方格。
在第三个样本中,政府有很多钱,所以反对派只能占据最后一个方格。