题目描述：

人类有n个星球，外星人有m个星球。

每个星球都有 初始的战舰数目 和 单位时间生产战舰的数目 两个属性。

n行m列的矩阵G， Gij表示人类i星球到外星人j星球所耗费的时间。

人类星球i攻击外星人星球j的战舰数目为：i初始数目+出发时间 * 生产率

外星人星球j的战舰数目：j初始数目 + （出发时间 + i到j耗费时间） * 它的生产率。

人类数目 >= 敌人数目，就能打败外星人星球j。

并且一个人类星球只能攻打一个外星人星球。

问，把所有外星人星球都打败的时间是多少。

解题报告：

二分花费时间（i到j能打败的花费时间已经预处理出来），满足花费时间的星球连接边。

匹配，看看匹配数目是否等于外星人星球数目。

满足的答案中最小值就是答案。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int num[2], match[250], cnt, x[2][250][2], g2[250][250], d[250][250], len[250 * 250];
bool vst[250]; vector<int> v[250];
bool find(int pos)
{
    for(int i = 0; i < v[pos].size(); i++)
        if (!vst[v[pos][i]])
        {
            vst[v[pos][i]] = 1;
            if (match[v[pos][i]] == -1 || find(match[v[pos][i]]))
            {
                match[v[pos][i]] = pos;
                return true;
            }
        }
    return false;
}
bool solve()
{
    memset(match, -1, sizeof(int) * (num[1] + 1));
    int ans = 0;
    for(int i = 0; i < num[0]; i++)
    {
        memset(vst, 0, sizeof(bool) * (num[1] + 1));
        ans += find(i);
    }
    return ans >= num[1];
}
int main()
{
    while(scanf("%d%d", &num[0], &num[1]) && (num[0] || num[1]))
    {
        int ans = 0x7fffffff; cnt = 0;
        for(int i = 0; i < 2; i++)for(int j = 0; j < num[i]; j++) scanf("%d%d", &x[i][j][0], &x[i][j][1]);
        for(int i = 0; i < num[0]; i++) for(int j = 0; j < num[1]; j++) scanf("%d", &d[i][j]);
        if (num[1] > num[0]){printf("IMPOSSIBLE\n"); continue;}
        for(int i = 0; i < num[0]; i++) for(int j = 0; j < num[1]; j++)
        {
            if (x[0][i][0] >= x[1][j][0] + d[i][j] * x[1][j][1]) {g2[i][j] = d[i][j]; len[cnt++] = d[i][j];}
            else if (x[0][i][1] <= x[1][j][1]) g2[i][j] = 0x7fffffff;
            else
            {
                int tmp1 = x[1][j][0] + d[i][j] * x[1][j][1] - x[0][i][0], tmp2 = x[0][i][1] - x[1][j][1];
                if (tmp1 % tmp2 == 0) g2[i][j] = tmp1 / tmp2 + d[i][j];
                else g2[i][j] = tmp1 / tmp2 + d[i][j] + 1;
                len[cnt++] = g2[i][j];
            }
        }
        sort(len, len + cnt);
        cnt = unique(len, len + cnt) - len;
        int l = 0, r = cnt - 1;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            for(int i = 0; i < num[0]; i++)
            {
                v[i].clear();
                for(int j = 0; j < num[1]; j++)
                    if (g2[i][j] <= len[mid]) v[i].push_back(j);
            }
            if (solve()) ans = min(ans, len[mid]), r = mid - 1;
            else l = mid + 1;
        }
        if (ans == 0x7fffffff) printf("IMPOSSIBLE\n");
        else printf("%d\n", ans);
    }
    return 0;
}