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 hx hit points and can cause dx 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 1018 days, please print none . Specially, if Pty can win now, the answer is 0.
Input
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.