描述

回到公元3024年，人类终于研发出了一项新技术，使他们能够征服外星种族。这项技术使得人类能够制造出名为“剑齿虎”的强大太空飞船，其威力足以匹敌外星人的防御猛犸象。当时，人类统治着多个行星，而其他一些行星仍处于外星人的控制之下。借助剑齿虎飞船，人类最终击败了外星人，这成为历史上的第一次行星战争。我们的目标是模拟这场远古战争，以验证一些历史假设。

制造每艘飞船所需的时间对于每个行星来说是固定的，但不同行星之间可能有所不同。我们称每个行星每年能够制造的飞船数量为该行星的生产率。注意，每个行星在模拟开始时已经拥有一定数量的飞船（初始数量）。行星在模拟开始时立即开始生产飞船，因此，如果一个行星初始有$n$艘飞船，生产率为$p$，则在第$i$年年初（年份从$0$开始计算），它将拥有$n + i \times p$艘飞船。

人类军队的总指挥官布拉德利·贝内特（Bradley Bennett）制定了战争策略。对于每个外星行星$A$，他选择一个对应的人类行星$P$，并在$P$上生产飞船，直到某一时刻将$P$上的所有飞船派往入侵行星$A$。每个外星行星不会被多个人类行星入侵，且每个人类行星也不会将其飞船派往多个不同的外星行星。

外星行星的防御力量来自其强大的猛犸象。每个外星行星初始拥有一定数量的猛犸象，并且每年生产一定数量的猛犸象（称为该行星的生产率）。当飞船与猛犸象发生战斗时，数量更多的一方将获胜。如果飞船获胜，外星行星将被击败。如果飞船和猛犸象的数量相等，飞船仍然获胜。

规划这一策略的难点在于，飞船到达外星行星需要一定时间，而在此期间外星人仍在生产猛犸象。每个人类行星到每个外星行星的航行时间是已知的。飞船只能在每年年初（飞船生产完成后）离开其行星，并在某年年初（猛犸象生产完成后）到达外星行星。

例如，考虑一个初始有$2$艘飞船、生产率为$3$的人类行星入侵一个初始有$2$只猛犸象、生产率为$2$的外星行星。两个行星之间的航行时间为$2$年，且飞船被命令在第$1$年离开。此时，人类行星将有$5$艘飞船出发。当它们到达外星行星时，将面对$8$只猛犸象，并在战斗中被击败。

贝内特决定制定一个计划，以最短的时间摧毁所有外星行星。你的任务是编写一个程序来生成这样的计划。输出应为击败所有外星行星所需的最短时间（以年为单位）。

输入

输入包含多个测试用例。每个测试用例的第一行包含两个数字$H$和$A$，分别表示人类控制的行星数量和外星控制的行星数量（均介于$1$到$250$之间）。测试用例的第二行包含$H$个非负整数$n_1\ m_1\ n_2\ m_2\ \ldots\ n_H\ m_H$，其中$n_i$表示第$i$个人类行星初始的飞船数量，$m_i$表示该行星的生产率。第三行包含$A$个非负整数，以相同格式描述外星行星的初始猛犸象数量和生产率。接下来的$H$行，每行包含$A$个正整数，其中第$i$行的第$j$个数表示从第$i$个人类行星到第$j$个外星行星所需的航行时间（年）。输入的最后一行是两个零。除$H$和$A$外，输入中的所有数字均介于$0$到$40000$之间。

输出

对于每个测试用例，输出一个整数，表示击败所有外星行星所需的最短时间。如果无法摧毁所有外星行星，则输出IMPOSSIBLE。

输入数据 1

2 1  
2 3 0 3  
2 2  
2  
2  
0 0  

输出数据 1

6  

来源

德黑兰 2006