Description
Little D recently discovered a small game online. The rules of the game are as follows:
- The goal of the game is to kill $n$ dragons in order from $1$ to $n$. Each dragon has an initial health value $a_i$. Each dragon also has a recovery ability; when it uses this ability, its health increases by $p_i$ each time until its health is non-negative. A dragon dies only if its health is exactly $0$ after an attack sequence.
- At the start of the game, the player possesses $m$ swords with known attack power. When facing a dragon, the player must choose one sword. Once the dragon is killed, that sword disappears, but as a reward, the player receives a brand new sword.
Little D finds this game quite boring, but the player who clears the game the fastest can win a qualification for ION2018. So, Little D decides to write a simple robot to help her clear the game. The robot follows these rules:
- When facing each dragon, the robot chooses the sword it currently possesses that has the highest attack power not exceeding the dragon's initial health $a_i$. If no such sword exists, it chooses the sword with the lowest attack power.
- When facing each dragon, the robot uses the chosen sword to attack the dragon a fixed number of times, $x$, reducing the dragon's health by $x \times \text{ATK}$.
- Afterward, the dragon continuously uses its recovery ability, recovering $p_i$ health each time. If the dragon's health is $0$ before or after any recovery, the dragon dies, and the player clears the level.
Clearly, the robot's number of attacks $x$ is the key to clearing the game as quickly as possible. Little D now knows all the attributes of each dragon. She wants to test you: do you know what the robot's attack count $x$ should be set to in order to clear the game with the minimum number of attacks?
Of course, if it is impossible to clear the game regardless of the setting, output -1.
Input
The input is read from the file dragon.in.
The first line contains an integer $T$, representing the number of data sets.
Each of the $T$ data sets consists of 5 lines:
- The first line of each data set contains two integers, $n$ and $m$, representing the number of dragons and the initial number of swords.
- The next line contains $n$ positive integers, where the $i$-th number represents the initial health $a_i$ of the $i$-th dragon.
- The next line contains $n$ positive integers, where the $i$-th number represents the recovery ability $p_i$ of the $i$-th dragon.
- The next line contains $n$ positive integers, where the $i$-th number represents the attack power of the sword rewarded after killing the $i$-th dragon.
- The next line contains $m$ positive integers, representing the attack power of the $m$ initially possessed swords.
Output
The output is written to the file dragon.out.
There are $T$ lines in total.
The $i$-th line contains an integer representing the minimum number of attacks $x$ that allows the robot to clear the game for the $i$-th data set. If no such answer exists, output -1.
Examples
Input 1
2 3 3 3 5 7 4 6 10 7 3 9 1 9 1000 3 2 3 5 6 4 8 7 1 1 1 1 1
Output 1
59 -1
Note 1
For the first data set: The initial swords have attack powers $\{1, 9, 10\}$. The first dragon has health $3$, so the sword with attack power $1$ is chosen. Attacking $59$ times deals $59$ damage. The dragon's health becomes $-56$, and after $14$ recoveries, its health is exactly $0$, so it dies. The sword with attack power $1$ disappears, and a sword with attack power $7$ is picked up. The available swords are $\{7, 9, 10\}$. The second dragon has health $5$, so the sword with attack power $7$ is chosen. Attacking $59$ times deals $413$ damage. The dragon's health becomes $-408$, and after $68$ recoveries, its health is exactly $0$, so it dies. The available swords are $\{3, 9, 10\}$. The third dragon has health $7$, so the sword with attack power $3$ is chosen. Attacking $59$ times deals $177$ damage. The dragon's health becomes $-170$, and after $17$ recoveries, its health is exactly $0$, so it dies. There is no way to clear the game with fewer than $59$ attacks, so the answer is $59$.
For the second data set: * There is no method that can kill both the first and second dragons, so it is impossible to clear the game; output -1.
Input 2
(See dragon/dragon2.in)
Output 2
(See dragon/dragon2.ans)
Subtasks
| Test Case ID | $n$ | $m$ | $p_i$ | $a_i$ | Attack Power | Other Constraints |
|---|---|---|---|---|---|---|
| 1 | $\le 10^5$ | $= 1$ | $= 1$ | $\le 10^5$ | $= 1$ | None |
| 2 | ||||||
| 3 | ||||||
| 4 | ||||||
| 5 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^6$ | $\le 10^6$ | Characteristic 1, 2 |
| 6 | ||||||
| 7 | ||||||
| 8 | $= 1$ | $= 1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Characteristic 1 |
| 9 | ||||||
| 10 | ||||||
| 11 | ||||||
| 12 | ||||||
| 13 | ||||||
| 14 | $= 10^5$ | $= 10^5$ | $= 1$ | $\le 10^{12}$ | $\le 10^6$ | No special constraints |
| 15 | ||||||
| 16 | $\le 10^5$ | $\le 10^5$ | All $p_i$ are prime | $\le 10^{12}$ | $\le 10^6$ | Characteristic 1 |
| 17 | ||||||
| 18 | ||||||
| 19 | ||||||
| 20 |
Characteristic 1: For any $i$, $a_i \le p_i$. Characteristic 2: $\text{LCM}(p_i) \le 10^6$, meaning the least common multiple of all $p_i$ is no greater than $10^6$. For all test cases, $T \le 5$, all weapon attack powers $\le 10^6$, and the least common multiple of all $p_i \le 10^{12}$.
Note
The intermediate results you use may be very large; pay attention to the variable types used to store intermediate results.