UVA1221 UVA1221

制造单艘飞船的耗时对同一颗行星是固定的，但在不同行星之间可能存在差异。我们将某颗行星**一年内可制造的飞船数量**定义为该行星的生产速率。需要注意的是，每颗行星在模拟开始前都拥有一定数量的初始飞船，模拟启动后行星便开始造舰：若某行星初始有 $n$ 艘飞船、生产速率为 $p$ ，则第1年开始时飞船数量为 $n+p$ ，第 $2$ 年开始时为 $n+2p$ （年份从 $0$ 开始计数），通用规律为**第 $k$ 年开始时**飞船数量为 $n + k \times p$。 人类军队总司令布拉德利·贝内特为这场战争制定了作战策略：对于每一颗外星行星 $A$ ，选定一颗对应的人类行星 $P$ ，在 $P$ 行星持续制造飞船，直至某一时刻将 $P$ 上所有飞船派出入侵 $A$ 。**每颗外星行星仅被一颗人类行星入侵，且每颗人类行星不会向两颗不同的外星行星派遣飞船**。 外星行星的防御力量来自其强大的猛犸象，每颗外星行星拥有一定数量的初始猛犸象，且每年会繁殖一定数量的猛犸象（该数量被称为外星行星的生产速率）。当飞船与猛犸象展开战斗时，兵力数量更多的一方获胜；若飞船数量与猛犸象数量相等，仍判定飞船获胜。飞船取胜后，该外星行星即被攻克。 制定该策略的难点在于，飞船前往外星行星需要耗费一定的航行时间，而这段时间内外星人仍会持续繁殖猛犸象。人类行星到各外星行星的飞船航行时间均为已知值，飞船**仅能在每年开始时**驶离母星（飞船完成生产后立即出发），且同样**在每年开始时**抵达外星行星（猛犸象完成繁殖后立即交战）。 贝内特希望制定一套能以**最短时间攻克所有外星行星**的作战计划，你的任务是编写程序生成该计划，输出攻克所有外星行星所需的最短时间（单位：年）。 ### 简要题意 --- 人类与外星人作战，人类有 $H$ 个星球，外星人有 $A$ 个星球，给出每个人类星球的飞船数和生产率及外星球的飞船数和生产率，并给出人类星球到达外星球需要的时间。**生产率**为某颗行星**一年内可制造的飞船数量**。 要求一个人类星球只能进攻一个外星星球。当人类星球的飞船数不少于外星球的飞船数时人类星球获胜。求使得人类所有星球获胜的最短时间。 ---

输入包含多组测试用例，**最后一行以两个0结束**。 每组测试用例第一行包含两个整数 $H$ 和 $A$ ，分别表示人类、外星人掌控的行星数量（均满足 $1 \le H,A \le 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$ 颗外星行星的飞船航行时间；

对于每组测试用例，输出一个整数，表示攻克所有外星行星的最短时间；若无法攻克所有外星行星，输出 `IMPOSSIBLE`。

除 $H$ 和 $A$ 外，输入中所有数字的取值范围均为 $0 \le val \le 40000$。 -------------- 一个**可能**的例子： 某人类行星初始有 $2$ 艘飞船、生产速率为 $3$ ，计划入侵一颗初始有 $2$ 头猛犸象、生产速率为$2$的外星行星，两行星间的航行时间为 $2$ 年，且飞船被下令在第$1$年驶离母星。 - 人类飞船出发数量：$2 + 1 \times 3 = 5$ 艘； - 外星猛犸象交战数量：$2 + (1+2) \times 2 = 8$ 头； 最终飞船因数量不足，战斗落败。 -------------------