CF1875A.Jellyfish and Undertale

Flowey has planted a bomb in Snowdin!

The bomb has a timer that is initially set to $b$. Every second, the timer will decrease by $1$. When the timer reaches $0$, the bomb will explode! To give the residents of Snowdin enough time to evacuate, you will need to delay the bomb from exploding for as long as possible.

You have $n$ tools. Each tool can only be used at most once. If you use the $i$-th tool, the timer will increase by $x_i$. However, if the timer is changed to an integer larger than $a$, the timer will be set to $a$ due to a bug.

More specifically, the following events will happen every second in the following order:

1. You will choose some (possibly none) of your tools that have not been used before. If you choose the $i$-th tool, and the bomb's timer is currently set to $c$, the timer will be changed to $\min(c + x_i, a)$.
2. The timer decreases by $1$.
3. If the timer reaches $0$, the bomb explodes.

Jellyfish now wants to know the maximum time in seconds until the bomb explodes if the tools are used optimally.

Flowey 在雪地镇（Snowdin）安装了一枚炸弹！

该炸弹的计时器初始值为 $b$。每过一秒，计时器减 $1$。当计时器减至 $0$ 时，炸弹将爆炸！为了给雪地镇的居民留出充足的撤离时间，你需要尽可能延迟炸弹的爆炸。

你拥有 $n$ 个工具，每个工具最多只能使用一次。若使用第 $i$ 个工具，计时器将增加 $x_i$。但若计时器因此变为大于 $a$ 的整数，则由于一个程序缺陷，计时器将被强制设为 $a$。

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

1. 你可以选择若干（也可以不选）尚未使用过的工具。若你选择第 $i$ 个工具，且此时炸弹计时器值为 $c$，则计时器将更新为 $\min(c + x_i, a)$。
2. 计时器减 $1$。
3. 若计时器变为 $0$，炸弹立即爆炸。

Jellyfish 想知道：在最优使用工具的前提下，炸弹最多能延迟多少秒后才爆炸？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 2000$). The description of the test cases follows.

The first line of each test case contains three integers $a$, $b$ and $n$ ($1 \leq b \leq a \leq 10^9$, $1 \leq n \leq 100$) — the maximum value of the bomb's timer, the initial value of the timer of the bomb and the number of tools.

The second line of each test contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \leq x_i \leq 10^9$) — the number the timer can increase by using the $i$-th tool.

Note that the sum of $n$ over all test cases is not bounded.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 的总和没有上界。

For each test case, output a single integer — the maximum time in seconds until the bomb explodes.

对于每个测试用例，输出一个整数——炸弹爆炸前的最大时间（单位：秒）。

Let $c$ denote the value of the bomb's timer. In the first test case:

• Second $1$: choose tool $1$ and $2$ at this second, then $c=5$; the timer decreases by $1$, then $c=4$.
• Second $2$: the timer decreases by $1$, then $c=3$.
• Second $3$: the timer decreases by $1$, then $c=2$.
• Second $4$: the timer decreases by $1$, then $c=1$.
• Second $5$: choose tool $3$, then $c=5$; the timer decreases by $1$, then $c=4$.
• Second $6$: the timer decreases by $1$, then $c=3$.
• Second $7$: the timer decreases by $1$, then $c=2$.
• Second $8$: the timer decreases by $1$, then $c=1$.
• Second $9$: the timer decreases by $1$, then $c=0$. The bomb explodes.

It can be proved that there is no way to use the tools such that the bomb explodes after more than $9$ seconds.

设 $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$ 秒后才爆炸。