Problem Description

Xiao D recently found a mini game online. The rules are as follows:

• The goal of the game is to kill $n$ dragons in order $1 \rightarrow n$. Each dragon has an initial health value $a_i$. At the same time, each dragon has a recovery ability: when it uses recovery, its health increases by $p_i$ each time until its health becomes non-negative. The dragon will only die when the attack ends and its health is exactly $0$.
• At the start of the game, the player has $m$ swords with known attack power. Each time facing a dragon, the player can only choose one sword. After killing the dragon, that sword disappears, but as a reward, the player obtains a brand-new sword.

Xiao D thinks this game is very boring, but the fastest player to clear it can get a qualification for ION2018, so Xiao D decides to write a simple robot to help her clear the game. Her robot follows these rules:

• Each time it faces a dragon, the robot chooses, among the swords it currently has, the one with the maximum attack power that does not exceed the dragon’s initial health as its weapon. If there is no such sword, it chooses the sword with the minimum attack power as its weapon.
• For each dragon, the robot uses the sword chosen in the previous step to attack the dragon a fixed $x$ times, reducing the dragon’s health by $x \times ATK$.
• Then, the dragon will keep using its recovery ability, recovering $p_i$ health each time. If before using recovery, or after some recovery, its health becomes $0$, then the dragon dies and the player clears this stage.

So obviously, the number of attacks is the key to whether the game can be cleared as fast as possible. Xiao D now knows all attributes of each dragon and wants to test you: what value should the robot’s attack count $x$ be set to, so that the game can be cleared with the minimum number of attacks?

Of course, if the game cannot be cleared no matter what it is set to, output $-1$.

Input Format

The first line contains an integer $T$, the number of test cases.

Then there are $T$ test cases, each containing $5$ lines.

• The first line of each test case contains two integers $n$ and $m$, representing the number of dragons and the number of initial swords;
• The next line contains $n$ positive integers; the $i$-th number is the initial health $a_i$ of the $i$-th dragon;
• The next line contains $n$ positive integers; the $i$-th number is the recovery value $p_i$ of the $i$-th dragon;
• The next line contains $n$ positive integers; the $i$-th number is the attack power of the sword rewarded after killing the $i$-th dragon;
• The next line contains $m$ positive integers, the attack powers of the $m$ initial swords.

Output Format

Output $T$ lines in total.

The $i$-th line contains one integer, indicating for the $i$-th test case the minimum attack count $x$ that allows the robot to clear the game. If no such answer exists, output $-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

59
-1

Hint

More Samples

Please download more samples in the attached file.

Sample 2

See dragon2.in and dragon2.ans in the attached file.

Explanation for Sample 1

Test case 1:

• The initial sword attack powers are $\{1,9,1000\}$. The health of dragon $1$ is $3$, so the sword with attack power $1$ is chosen. Attack $59$ times, dealing $59$ damage. The dragon’s health becomes $-56$. After recovering $14$ times, its health becomes exactly $0$, so it dies.

• The sword with attack power $1$ disappears, and a sword with attack power $7$ is picked up. Now the sword attack powers are $\{7,9,1000\}$. The health of dragon $2$ is $5$, so the sword with attack power $7$ is chosen. Attack $59$ times, dealing $413$ damage. The dragon’s health becomes $-408$. After recovering $68$ times, its health becomes exactly $0$, so it dies.

• Now the sword attack powers are $\{3,9,1000\}$. The health of dragon $3$ is $7$, so the sword with attack power $3$ is chosen. Attack $59$ times, dealing $177$ damage. The dragon’s health becomes $-170$. After recovering $17$ times, its health becomes exactly $0$, so it dies.

• There is no way to clear the game with fewer than $59$ attacks, so the answer is $59$.

Test case 2: There is no method that can kill both the first dragon and the second dragon, so the game cannot be cleared. Output $-1$.

Subtasks

::cute-table{tuack}

Property 1 means: for any $i$, $a_i \le p_i$.

Property 2 means: $\operatorname{lcm}(p_i) \le 10^6$, i.e. the least common multiple of all $p_i$ is at most $10^6$.

For all test points, $T \le 5$, all weapon attack powers $\le 10^6$, and the least common multiple of all $p_i$ is $\le 10^{12}$.

It is guaranteed that $T$, $n$, and $m$ are all positive integers.

Notes

The intermediate results you use may be very large, so pay attention to the variable types used to store them.

Translated by ChatGPT 5