{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003ePty 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. \u003cbr\u003e\u003cbr\u003eThe monster is also leading a team of soldiers. And to complete the challenge Pty should beat these soldiers. \u003cbr\u003e\u003cbr\u003eThe 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. \u003cbr\u003e\u003cbr\u003eThe 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. \u003cbr\u003e\u003cbr\u003eBoth 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. \u003cbr\u003e\u003cbr\u003ePty wants to know the minimum x that he will complete the challenge if it take place on x days later.\u003cbr\u003e\u003cbr\u003eIf Pty can’t win the monster in $10^{18}$ days, please print none . Specially, if Pty can win now, the answer is 0. \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"An integer T in the first line, it is the number of tesecases. And there are T cases later.\u003cbr\u003e\u003cbr\u003eIn 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. \u003cbr\u003e\u003cbr\u003eIn 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. \u003cbr\u003e\u003cbr\u003eIn the next m lines, also contains 4 integers. They are the information of the soldier in the monster’s team. \u003cbr\u003e\u003cbr\u003e$(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)$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output ’none’ or integer means the minimum of x in one line. "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 2\r\n2 3 1 3\r\n3 2 4 3\r\n1 2 2 3\r\n3 3 4 2\r\n4 1 1 3\r\n1 1\r\n1 1 1 1\r\n1 1 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\nnone\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}