← 返回题目列表

Codeforces · 1875/A

A. 水母和传说之下

中文机器翻译题面 查看原题

花花在雪町安放了炸弹!

炸弹有一个计时器,最初设置为$$$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$$$秒后爆炸。