CF1862F.Magic Will Save the World
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A portal of dark forces has opened at the border of worlds, and now the whole world is under a terrible threat. To close the portal and save the world, you need to defeat n monsters that emerge from the portal one after another.
Only the sorceress Vika can handle this. She possesses two magical powers — water magic and fire magic. In one second, Vika can generate w units of water mana and f units of fire mana. She will need mana to cast spells. Initially Vika have 0 units of water mana and 0 units of fire mana.
Each of the n monsters that emerge from the portal has its own strength, expressed as a positive integer. To defeat the i -th monster with strength si , Vika needs to cast a water spell or a fire spell of at least the same strength. In other words, Vika can spend at least si units of water mana on a water spell, or at least si units of fire mana on a fire spell.
Vika can create and cast spells instantly. Vika can cast an unlimited number of spells every second as long she has enough mana for that.
The sorceress wants to save the world as quickly as possible, so tell her how much time she will need.
输入格式
Each test consists of several test cases. The first line of each test contains a single integer t ( 1≤t≤100 ) — the number of test cases. This is followed by a description of the test cases.
The first line of each test case contains two integers w , f ( 1≤w,f≤109 ) — the amount of water and fire mana that Vika can generate per second.
The second line of each test case contains a single integer n ( 1≤n≤100 ) — the number of monsters.
The third line of each test case contains n integers s1,s2,s3,…,sn ( 1≤si≤104 ) — the strengths of the monsters.
It is guaranteed that the sum of n over all test cases does not exceed 100 .
输出格式
For each test case, output a single integer — the minimum time in seconds that Vika will need to defeat all the monsters.
输入输出样例
输入#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
说明/提示
In the first sample, after the first second, Vika can spend 2 units of fire mana to kill the first monster. Then she has 2 units of water mana and 1 unit of fire mana. After the third second, she will have 6 units of water mana and 7 units of fire mana at her disposal. This will be enough to immediately kill the second and third monsters.