Problem 2A.拆弹专家

时间限制：2s

空间限制：256MB

题目描述

笨小羊遇到了一颗炸弹！

炸弹有一个计时器，最初设置为\(b\)。每一秒，计时器都会减少1。当计时器到达0，炸弹会爆炸的！
笨小羊需要尽可能长时间地推迟炸弹的爆炸。

笨小羊有\(n\)个工具。每个工具最多只能用一次。如果你使用第\(i\)个工具，计时器将增加\(x_i\)。
但是，如果计时器更改为大于\(a\)，计时器将设置为\(a\)。

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

1 笨小羊将选择一些（可能没有）以前从未使用过的工具。如果选择第\(i\)个工具，炸弹的计时器目前设置为\(c\)，计时器将更改为\(min(c+x_i,a)\).
2 计时器减少了1。
3 如果计时器达到0，炸弹爆炸了。

如果工具得到最佳使用，笨小羊现在想知道炸弹爆炸的最大时间（以秒为单位）.

数据格式

输入

每个测试都包含多个测试用例。第一行包含测试用例的数量\(t\)（\(1≤t≤2000\)）。测试用例的描述如下。

每个测试用例的第一行包含三个整数\(a\)，\(b\)和\(n\)（\(1≤b≤a≤10^9\)，\(1≤n≤100\)）—\(a\),\(b\),\(n\)分别表示炸弹计时器的最大值、炸弹计时器的初始值和工具数量。

每个测试的第二行包含\(n\)个整数\(x_1\),\(x_2\),...,\(x_n\)（\(1≤x_i≤10^9\)）—计时器可以使用第\(i\)个工具来增加\(x_i\)的时间。

请注意，总和\(n\)在所有测试用例上都是无限制的。70%的数据点t<=20。最后30%t=2000.

输出

一行，一个非负整数\(k\)，表示炸弹爆炸前的最大时间。

样例

输入

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

输出

9
21

样例解释

让\(c\)表示炸弹计时器的值。

在第一个测试用例中：
第1秒：在这一秒选择工具1和2，然后c=5；计时器减少1，然后c＝4。

第2秒：计时器减少1，然后c=3。

第3秒：计时器减少1，然后c=2。

第4秒：计时器减少1，然后c=1。

第5秒：选择工具3，然后𝑐=5.计时器减少1，然后𝑐=4.

第6秒：计时器减少1，然后𝑐=3.

第7秒：计时器减少1，然后𝑐=2.

第8秒：计时器减少1，然后𝑐=1.

第9秒：计时器减少1，然后𝑐=0炸弹爆炸了。

可以证明，没有办法使用这种工具，使炸弹在9秒以上爆炸。