{"trustable":false,"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Back to year 3024, humans finally developed a new technology that enables them to conquer the alien races. The new technology made it possible to produce huge spaceships known as Saber Tooth spaceships as powerful as the aliens\u0027 defending mammoths. At that time, humans ruled several planets while some others were under control of the aliens. Using Saber Tooth ships, humans finally defeated aliens and this became the first Planet War in history. Our goal is to run a simulation of the ancient war to verify some historical hypotheses. \n \u003cbr\u003e \n \u003cbr\u003eProducing each spaceship takes an amount of time which is constant for each planet but may vary among different planets. We call the number of spaceships each planet can produce in a year, the \n \u003ci\u003eproduction rate\u003c/i\u003e of that planet. Note that each planet has a number of spaceships in it initially (before the simulation starts). The planets start producing ships when the simulation starts, so if a planet has \n \u003ci\u003en\u003c/i\u003eships initially, and has the production rate \n \u003ci\u003ep\u003c/i\u003e, it will have \n \u003ci\u003en + p\u003c/i\u003e ships at the beginning of year 1, and \n \u003ci\u003en + i × p\u003c/i\u003e ships at the beginning of year \n \u003ci\u003ei\u003c/i\u003e (years are started from zero). \n \u003cbr\u003e \n \u003cbr\u003eBradley Bennett, the commander in chief of the human armies, decided a strategy for the war. For each alien planet A, he chooses a corresponding human planet P, and produces spaceships in P until a certain moment at which he sends all spaceships in P to invade the planet A. No alien planet is invaded by two human planets and no human planet sends its spaceships to two different alien planets. \n \u003cbr\u003e \n \u003cbr\u003eThe defense power of the alien planets comes from their powerful mammoths. Each alien planet contains a number of mammoths initially and produces a number of mammoths each year (called the production rate of the planet). When a fight between spaceships and mammoths takes place, the side having the greater number of troops is the winner. If the spaceships win, the alien planet is defeated. In case the number of mammoths and spaceships are equal, the spaceships win. \n \u003cbr\u003e \n \u003cbr\u003eThe difficulty with planning this strategy is that it takes some time for the spaceships to reach the alien planets, and during this time, the aliens produce mammoths. The time required for spaceships to travel from each human planet to each alien planet is known. The ships can leave their planets only at the beginning of years (right after the ships are produced) and reach the alien planets at the beginning of years too (right after the mammoths are produced). \n \u003cbr\u003e \n \u003cbr\u003eAs an example, consider a human planet with two initial spaceships and production rate three invading an alien planet with two initial mammoths and production rate two. The time required to travel between the two planets is two years and the ships are ordered to leave at year one. In this case, five ships leave the human planet. When they reach the alien planet, they confront eight mammoths and will be defeated during the fight. \n \u003cbr\u003e \n \u003cbr\u003eBennett decided to prepare a plan that destroys every alien planet in the shortest possible time. Your task is to write a program to generate such a plan. The output is the shortest possible time (in years) in which every alien planet is defeated. \n \u003cbr\u003e \n\u003c/div\u003e\n\u003cbr\u003e人类掌握了H个星球,外星人掌握了A个星球。\n\u003cbr\u003e人类想占领所有的外星。人类的每个星球每年都能生产能生产军舰。外星人的星球也是。\n\u003cbr\u003e如果一个星球初始有a个军舰,每年可以生产p个军舰,那么x年以后就有a+x*p个。\n\u003cbr\u003e人类打算先生产军舰,之后进攻。每个人类星球只会经过一个外星球,一个外星球也只会被一个人类星球进攻。如果人类星球的军舰数大于等于外星球的军舰数,就能占领这个星球。\n求最少多少年后就能占领所有的外星球。"}},{"title":"Input","value":{"format":"HTML","content":"There are multiple test cases in the input. The first line of each test case contains two numbers H and A which are the number of planets under the control of humans and aliens respectively (both between 1 and 250). The second line of the test case contains H non-negative integers \n\u003ci\u003en\u003csub\u003e1\u003c/sub\u003e m\u003csub\u003e1\u003c/sub\u003e n\u003csub\u003e2\u003c/sub\u003e m\u003csub\u003e2\u003c/sub\u003e … n\u003csub\u003eH\u003c/sub\u003e m\u003csub\u003eH\u003c/sub\u003e\u003c/i\u003e. The number n \n\u003csub\u003ei\u003c/sub\u003e is the initial number of Saber Tooth spaceships in the ith human planet and m \n\u003csub\u003ei\u003c/sub\u003e is the production rate of that planet. The third line contains A non-negative integers which specify the initial number of mammoths and the production rate of the alien planets in the same format as the second line. After the third line, there are H lines each containing A positive integers. The jth number on the ith line shows how many years it takes a spaceship to travel from the ith human planet to the jth alien planet. The last line of the input contains two zero numbers. Every number in the input except H and A is between 0 and 40000. \n\u003cbr\u003e\n\u003cbr\u003e有多组测试数据,第一行两个整数H和A,表示人类星球的数量和外星球的数量。\n\u003cbr\u003e第二行有H对整数,分别表示第i个人类星球初始的军舰数和每年可以生产的军舰数。\n\u003cbr\u003e第三行有A对整数,分别表示第i个外星球初始的军舰数和每年可以生产的军舰数。\n\u003cbr\u003e接下来H行,每行A个整数,表示第i个人类星球到第j个外星球需要花的时间。"}},{"title":"Output","value":{"format":"HTML","content":"The output for each test case contains a single integer which is the minimum time in which all alien planets can be defeated. If it is impossible to destroy all alien planets, the output should be IMPOSSIBLE. \n\u003cbr\u003e\n输出一个整数,表示最少多少年之后,可以占领所有的外星球。\n如果不能占领所有外星球,输出IMPOSSIBLE."}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2 1\n2 3 0 3\n2 2\n2\n2\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e6\u003c/pre\u003e"}}]}