花花在雪町安放了炸弹!
炸弹有一个计时器,最初设置为$$$b$$$。每秒,计时器都会减少 $$$1$$$。当计时器到达 $$$0$$$ 时,炸弹就会爆炸!为了给雪町居民足够的时间撤离,你需要尽可能延迟炸弹爆炸。
你有 $$$n$$$ 工具。每个工具最多只能使用一次。如果您使用第 $$$i$$$ 个工具,计时器将增加 $$$x_i$$$。但是,如果将计时器更改为大于 $$$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$$$ 之和不受限制。
输出
对于每个测试用例,输出一个整数 - 炸弹爆炸的最长时间(以秒为单位)。
示例
输入 #1
2 5 3 3 1 1 7 7 1 5 1 2 5 6 8
输出 #1
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$$$,然后$$$c=5$$$;计时器减少$$$1$$$,则$$$c=4$$$。
- 第二个$$$6$$$:计时器减少$$$1$$$,然后$$$c=3$$$。
- 第二个$$$7$$$:计时器减少$$$1$$$,然后$$$c=2$$$。
- 第二个$$$8$$$:计时器减少$$$1$$$,然后$$$c=1$$$。
- 第二个$$$9$$$:计时器减少$$$1$$$,然后$$$c=0$$$。炸弹爆炸了。
可以证明,没有办法使用工具让炸弹在$$$9$$$秒后爆炸。