题目描述

Flowey 在 Snowdin 安放了一颗炸弹！

这颗炸弹有一个初始为 $b$ 的倒计时定时器。每过一秒，定时器会减少 $1$。当定时器归零时，炸弹就会爆炸！为了让 Snowdin 的居民有足够的时间撤离，你需要尽可能延迟炸弹爆炸的时间。

你有 $n$ 个工具。每个工具最多只能使用一次。如果你使用第 $i$ 个工具，定时器会增加 $x_i$。然而，由于一个 bug，如果定时器被调整到大于 $a$ 的整数，定时器会被设置为 $a$。

更具体地说，每一秒会按以下顺序发生如下事件：

1. 你可以选择一些（也可以一个都不选）之前未用过的工具。如果你选择了第 $i$ 个工具，并且当前炸弹定时器为 $c$，则定时器会变为 $\min(c + x_i, a)$。
2. 定时器减少 $1$。
3. 如果定时器变为 $0$，炸弹爆炸。

Jellyfish 现在想知道，如果你最优地使用工具，炸弹最多能在多少秒后爆炸。

输入格式

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 2000$）。接下来是每组测试用例的描述。

每组测试用例的第一行包含三个整数 $a$、$b$ 和 $n$（$1 \leq b \leq a \leq 10^9$，$1 \leq n \leq 100$）——炸弹定时器的最大值、初始值以及工具数量。

每组测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \leq x_i \leq 10^9$）——使用第 $i$ 个工具可以让定时器增加的数值。

注意，所有测试用例中 $n$ 的总和没有限制。

输出格式

对于每组测试用例，输出一个整数，表示炸弹最多能在多少秒后爆炸。

说明/提示

设 $c$ 表示炸弹定时器的当前值。在第一个测试用例中：

• 第 $1$ 秒：选择工具 $1$ 和 $2$，此时 $c=5$；定时器减 $1$，$c=4$。
• 第 $2$ 秒：定时器减 $1$，$c=3$。
• 第 $3$ 秒：定时器减 $1$，$c=2$。
• 第 $4$ 秒：定时器减 $1$，$c=1$。
• 第 $5$ 秒：选择工具 $3$，$c=5$；定时器减 $1$，$c=4$。
• 第 $6$ 秒：定时器减 $1$，$c=3$。
• 第 $7$ 秒：定时器减 $1$，$c=2$。
• 第 $8$ 秒：定时器减 $1$，$c=1$。
• 第 $9$ 秒：定时器减 $1$，$c=0$。炸弹爆炸。

可以证明，没有任何方法能让炸弹在 $9$ 秒后才爆炸。

由 ChatGPT 4.1 翻译

样例

2
5 3 3
1 1 7
7 1 5
1 2 5 6 8

9
21