← 返回题目列表

Codeforces · 1862/F

F. 魔法将拯救世界

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

黑暗势力的门户已经在世界的边界打开,现在整个世界都面临着可怕的威胁。为了关闭传送门并拯救世界,你需要击败从传送门中出现的一个又一个$$$n$$$怪物。

只有女巫维卡可以处理这个。她拥有两种魔法力量——水魔法和火魔法。一秒钟内,维卡可以产生 $$$w$$$ 单位的水法力和 $$$f$$$ 单位的火法力。她需要法力来施展法术。最初,维卡拥有 $$$0$$$ 单位的水法力和 $$$0$$$ 单位的火法力。

从传送门中出现的每个 $$$n$$$ 怪物都有自己的强度,以正整数表示。为了击败实力为 $$$s_i$$$ 的第 $$$i$$$ 怪物,维卡需要施展至少相同强度的水系法术或火系法术。换句话说,维卡可以在水法术上花费至少 $$$s_i$$$ 单位的水法力,或者在火法术上花费至少 $$$s_i$$$ 单位的火法力。

维卡可以立即创造和施展法术。维卡每秒可以施展无限数量的法术,只要她有足够的法力即可。

女巫想要尽快拯救世界,所以告诉她需要多少时间。

输入

每个测试由多个测试用例组成。每个测试的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) - 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$w$$$、$$$f$$$ ($$$1 \le w, f \le 10^9$$$) — Vika 每秒可以产生的水和火魔法值。

每个测试用例的第二行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 怪物的数量。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$s_1, s_2, s_3, \dots, s_n$$$ ($$$1 \le s_i \le 10^4$$$) — 怪物的强度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$100$$$。

输出

对于每个测试用例,输出一个整数 - Vika 击败所有怪物所需的最短时间(以秒为单位)。

示例

输入 #1

4
2 3
3
2 6 7
37 58
1
93
190 90
2
23 97
13 4
4
10 10 2 45

输出 #1

3
2
1
5

注意

在第一个示例中,第一秒后,Vika 可以花费 $$$2$$$ 单位的火焰法力来杀死第一个怪物。然后她有 $$$2$$$ 单位的水法力和 $$$1$$$ 单位的火法力。第三秒后,她将拥有 $$$6$$$ 单位的水法力和 $$$7$$$ 单位的火法力可供使用。这足以立即杀死第二个和第三个怪物。