Against Mammoths

In the year 3024, humanity finally developed the technology to challenge the alien races. Massive warships called Saber Tooth ships, as powerful as the aliens' defending mammoths, could now be built. Humans ruled several planets, and so did the aliens. Using Saber Tooth ships, humanity fought and won the first Planet War in history. Your task is to simulate that ancient war to test a few historical hypotheses.

Each human planet builds ships at its own constant rate. The production rate of a planet is the number of ships it builds per year. Every planet also starts with some ships before the simulation begins. Counting years from $0$, a planet that starts with $n$ ships and has production rate $p$ owns $n + p$ ships at the start of year $1$, and $n + i \times p$ ships at the start of year $i$.

Commander Bradley Bennett fixes a strategy: for every alien planet he picks one human planet, lets it build ships, and at a chosen moment sends all of that planet's ships to invade the alien planet. No alien planet is attacked by two human planets, and no human planet attacks two alien planets.

Each alien planet is defended by mammoths. It starts with some mammoths and breeds more every year at its own production rate, so at the start of year $i$ it holds (initial mammoths) $+\, i \times (\text{rate})$ mammoths. When ships meet mammoths, the larger army wins; if the two counts are equal, the ships win. If the ships win, the alien planet is destroyed.

Ships take time to travel. The travel time, in whole years, between every human planet and every alien planet is given. A fleet may leave only at the start of a year (right after that year's ships are produced) and arrives only at the start of a year (right after that year's mammoths are produced). So if a fleet leaves a human planet at the start of year $L$ and the travel time is $t$, it arrives at the start of year $L + t$ carrying $n + L \times p$ ships and faces (initial mammoths) $+\,(L + t) \times (\text{rate})$ mammoths.

For example, a human planet with $2$ initial ships and production rate $3$ attacks an alien planet with $2$ initial mammoths and production rate $2$; the travel time is $2$ years and the fleet is ordered to leave at year $1$. Then $2 + 3 \times 1 = 5$ ships depart, and on arrival at year $3$ they face $2 + 2 \times 3 = 8$ mammoths, so the fleet is destroyed.

Bennett wants a plan that destroys every alien planet as early as possible; that is, he minimizes the year in which the last alien planet falls. Output that earliest possible year.

The input contains several test cases. The first line of each test case has two integers $H$ and $A$: the number of human and alien planets respectively (each between $1$ and $250$).

The second line has $H$ pairs of non-negative integers $n_1\ m_1\ n_2\ m_2 \dots n_H\ m_H$, where $n_i$ is the initial number of ships and $m_i$ is the production rate of the $i$-th human planet.

The third line has $A$ pairs of non-negative integers in the same format, giving the initial number of mammoths and the production rate of each alien planet.

Then follow $H$ lines, each with $A$ positive integers; the $j$-th number on the $i$-th line is the travel time in years from the $i$-th human planet to the $j$-th alien planet.

The input ends with a line containing two zeros. Every number other than $H$ and $A$ is between $0$ and $40000$.

For each test case, print a single line: the minimum number of years in which all alien planets can be destroyed. If destroying them all is impossible, print IMPOSSIBLE instead.