Pty plays game

Pty is playing a game, where he is leading a team of soldiers. He is facing a challenge in the game. He plans to complete the challenge x days later.

The monster is also leading a team of soldiers. And to complete the challenge Pty should beat these soldiers.

The battle will execute as follows. At first, the first soldier of both teams will fight first. When a soldier’s hit points becomes 0,the soldier will be replaced by the next soldier in the same team.A team is considered a victory only if there is any soldier alive but nobody is alive in the opposite team finally.

The soldier x have ${h_x}$ hit points and can cause ${d_x}$ damage to the enemy per second. Notice that the seconds of a fight may not be an integer.

Both Pty and the monster will train their soldiers continuously, so the hit points and damage per second of all the soldiers will increase every day.

Pty wants to know the minimum x that he will complete the challenge if it take place on x days later.

If Pty can’t win the monster in $10^{18}$ days, please print none . Specially, if Pty can win now, the answer is 0.

An integer T in the first line, it is the number of tesecases. And there are T cases later.

In each case, two integers in the first line n,m, which is the numbers of soldiers in the Pty’s team and the monster’s team.

In the next n lines, each line contains 4 integers. They means the hit point, the increment of hit point every day, the damage and the increment of damage every day.

In the next m lines, also contains 4 integers. They are the information of the soldier in the monster’s team.

$(1 \leq n,m\leq 10^5, \sum (n+m) \leq 2\times 10^6,0 \leq h_x,d_x \leq 10^6,0\leq increment \leq 10^3)$

For each test case, output ’none’ or integer means the minimum of x in one line.

2
3 2
2 3 1 3
3 2 4 3
1 2 2 3
3 3 4 2
4 1 1 3
1 1
1 1 1 1
1 1 1 1

1
none

2021“MINIEYE杯”中国大学生算法设计超级联赛（10）