故障机器人想活下去

Problem Description

故障机器人共有 $x$ 点生命值，他在高塔中遭遇了 $n$ 个敌人，在和第 $i$ 个敌人战斗后故障机器人会损失 $a_i$ 点生命值，在战斗结束后生命值降低到 $0$ 或以下时故障机器人会死亡。同时，故障机器人手上有 $k$ 个烟雾弹，在战斗开始时，他可以选择消耗 $1$ 个烟雾弹来逃离这场战斗，如此战斗会直接结束，故障机器人在这场战斗中不会损失生命值。 故障机器人将依次与 $n$ 个敌人进行战斗，他想知道在最优策略下，最多能存活到第几场战斗结束，你能帮帮故障机器人吗？

Input

一行一个正整数 $t$ ($1 \leq t \leq 30$), 表示有 $t$ 组数据。 每组数据的第一行有三个整数 $n, x, k$ ($1 \leq n \leq 10^5, 1 \leq x \leq 10^9,0 \leq k \leq 10^5$)，分别表示敌人的数量，故障机器人的初始生命值和烟雾弹的数量。 每组数据的第二行有 $n$ 个正整数，其中第 $i$ 个正整数 $a_i$ ($1 \leq a_i \leq 10^5$) 表示故障机器人与第 $i$ 个敌人战斗后损失的生命值。

Output

对于每组数据输出一行 每行一个整数，表示故障机器人最多能存活到第几场战斗结束。如果故障机器人不能在任何一场战斗结束时存活，输出 $0$。

Sample Input

3
5 10 1
3 4 5 2 7
3 7 0
2 3 4
10 20 3
6 12 9 4 10 1 3 4 2 1

Sample Output

4
2
8

Hint

对第一组样例的解释：故障机器人共有 $10$ 点生命值与 $1$ 个烟雾弹，在与第 $1$ 个敌人战斗后损失了 $3$ 点生命值，在与第 $2$ 个敌人战斗后损失了 $4$ 点生命值，使用烟雾弹结束与第 $3$ 个敌人的战斗，在与第 $4$ 个敌人战斗后损失了 $2$ 点生命值，在与第 $5$ 个敌人的战斗中故障机器人的生命值不足 $7$ 点，死亡，因此故障机器人最多能存活到第 $4$ 场战斗结束，可以证明不存在比 $4$ 更大的答案。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）