题目描述

有 n 个人类星球，m 个外星球，每个星球上开始有 sh 艘飞船，之后每年会生产 p 艘飞船。每个星球的生产效率是固定的，不同星球之间会有不同。人类想要战胜所有的外星球需要满足以下条件:
每个人类星球和每个外星球有一定的距离（需要耗费 k 年才能到达）。战争在第 0 年开始，第一年，星球上有 sh + 1 * p。如果在第 a 年，人类星球 H 向外星球 A 宣战，那么人类会带上 sh + p * a 艘飞船进攻（飞行过程中无法制作飞船），经过 k 年后到达外星球，这时外星球飞船的数量为 sh' + p' * (a + k)，如果这时人类飞船的数量 >= 外星球飞船的数量，那么就会战胜这个外星球，每个人类星球只能攻击一个外星球，一个外星球只能被一个人类星球攻击，问最少需要多少年人类才能全部战胜所有的外星球。如果不能打完所有外星球就输出 IMPOSSIBLE。

输入格式

第一行两个整数 n, m，表示 n 个人类星球，m 个外星球 1 <= n, m <= 250；
第二行有 n 对非负整数 wi, pi，表示第 ni 个星球的初始飞船数为 wi，生成效率为pi；
第三行有 m 对非负整数 xi, yi，表示第mi 个星球的初始飞船数为xi，生成效率为yi；
接下来 n 行，每行 m 个整数，表示第 i 个人类星球到第 j 个外星球的飞行时间。

输出格式

输出所有外星球被击败的最小时间，如果不能击败所有的外星球则输出 “IMPOSSIBLE”

样例输入

2 1
2 3 0 3
2 2
2
2

样例输出

6

数据范围

对于 30%的数据，1 <= n, m <= 50，0 <= wi, pi, xi, yi, ki <= 100；
对于 100%的数据，1 <= n, m <= 250，0 <= wi, pi, xi, yi, ki <= 40000。

限制

1s

样例解释

第 1 号人类星球在 4 年后飞出，飞船数量 = 2 + 3 * 4 = 14，第 2 号则为 0 + 3 * 4 = 12；
第 1 号外星球生产了 8 年，飞船数量 = 2 + 2 * (4 + 2) = 14 <= 14，外星球被打败。

来源

CWOI新高二专题测试十三