매머드에 맞서서

서기 3024년, 인류는 마침내 외계 종족에 맞설 기술을 손에 넣었다. 외계인의 방어 병기인 매머드에 필적하는 거대한 전함, 세이버투스(Saber Tooth) 함선을 만들 수 있게 된 것이다. 당시 인류와 외계인은 각각 여러 행성을 지배하고 있었고, 인류는 세이버투스 함선으로 역사상 최초의 행성 전쟁에서 승리했다. 여러분의 임무는 그 옛 전쟁을 시뮬레이션하여 몇 가지 역사적 가설을 검증하는 것이다.

각 인류 행성은 저마다 일정한 속도로 함선을 생산한다. 행성이 1년에 생산하는 함선 수를 그 행성의 생산률이라 한다. 또한 모든 행성은 시뮬레이션 시작 전에 이미 일정한 수의 함선을 보유한다. 연도를 $0$부터 센다고 할 때, 처음에 함선 $n$대를 가지고 생산률이 $p$인 행성은 $1$년 초에 $n + p$대를, $i$년 초에 $n + i \times p$대를 보유한다.

총사령관 브래들리 베넷은 다음과 같은 전략을 세운다. 각 외계 행성마다 인류 행성 하나를 골라 함선을 생산하게 하고, 정해진 시점에 그 행성의 모든 함선을 보내 해당 외계 행성을 침공한다. 어떤 외계 행성도 두 인류 행성에게 공격받지 않으며, 어떤 인류 행성도 두 외계 행성을 공격하지 않는다.

각 외계 행성은 매머드로 방어한다. 처음에 일정한 수의 매머드를 보유하고 매년 자신의 생산률만큼 매머드를 늘리므로, $i$년 초에는 (초기 매머드 수) $+\, i \times (\text{생산률})$마리의 매머드를 갖는다. 함선과 매머드가 맞붙으면 수가 더 많은 쪽이 이기며, 양쪽 수가 같으면 함선이 이긴다. 함선이 이기면 그 외계 행성은 파괴된다.

함선의 이동에는 시간이 걸린다. 모든 인류 행성과 외계 행성 사이의 이동 시간(정수 연 단위)이 주어진다. 함대는 오직 연도 초(그 해의 함선이 생산된 직후)에만 출발할 수 있고, 오직 연도 초(그 해의 매머드가 생산된 직후)에만 도착한다. 따라서 어떤 함대가 $L$년 초에 인류 행성을 떠나고 이동 시간이 $t$라면, 그 함대는 $n + L \times p$대의 함선을 싣고 $L + t$년 초에 도착하며 (초기 매머드 수) $+\,(L + t) \times (\text{생산률})$마리의 매머드와 마주한다.

예를 들어 초기 함선 $2$대, 생산률 $3$인 인류 행성이 초기 매머드 $2$마리, 생산률 $2$인 외계 행성을 공격한다고 하자. 이동 시간은 $2$년이고 함대는 $1$년에 출발하도록 명령받았다. 그러면 $2 + 3 \times 1 = 5$대가 출발하여 $3$년 초에 도착하고 $2 + 2 \times 3 = 8$마리의 매머드와 마주하므로 전멸한다.

베넷은 모든 외계 행성을 가능한 한 이른 시점에 파괴하는 계획을 원한다. 즉, 마지막 외계 행성이 파괴되는 연도를 최소화하려 한다. 그 가능한 가장 이른 연도를 출력하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $H$와 $A$가 주어진다. 각각 인류 행성과 외계 행성의 개수이며, 둘 다 $1$ 이상 $250$ 이하이다.

둘째 줄에는 음이 아닌 정수 $H$쌍 $n_1\ m_1\ n_2\ m_2 \dots n_H\ m_H$가 주어진다. $n_i$는 $i$번째 인류 행성의 초기 함선 수, $m_i$는 그 행성의 생산률이다.

셋째 줄에는 같은 형식으로 음이 아닌 정수 $A$쌍이 주어지며, 각 외계 행성의 초기 매머드 수와 생산률을 나타낸다.

그 다음 $H$개의 줄이 이어지고 각 줄에는 양의 정수 $A$개가 있다. $i$번째 줄의 $j$번째 수는 $i$번째 인류 행성에서 $j$번째 외계 행성까지의 이동 시간(연)이다.

입력은 두 개의 $0$이 적힌 줄로 끝난다. $H$와 $A$를 제외한 모든 수는 $0$ 이상 $40000$ 이하이다.

각 테스트 케이스마다 한 줄에, 모든 외계 행성을 파괴할 수 있는 최소 연수를 출력하라. 모두 파괴하는 것이 불가능하면 대신 IMPOSSIBLE을 출력하라.