logo AlgoBeat OnlineJudge
登录 注册

#101896. [BZOJ 1896] pku3689 equations

内存限制:64 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出3个长度均为n的正整数序列: A1;A2;A3;:::An; B1;B2;B3;:::Bn; C1;C2;C3;:::Cn;以及m对整数,你的目标是找到一组非负实数解满足如下方程组: A1X1 + A2X2 + A3X3 + ::: + AnXn = Si B1X1 + B2X2 + B3X3 + ::: + BnXn = Ti 并且使得C1X1 + C2X2 + C3X3 + ::: + CnXn的值最大。

输入格式

第一行包含两个整数n和m。以下n行每行包含3个整数Ai;Bi;Ci。再下面m行每行包含两个整数Si;Ti。

输出格式

对于每对输出可得的最大值,与答案的误差不超过10^-4算作正确。

如果不存在,则输出“IMPOSSIBLE”。

样例

样例输入

2 2
2 2 2
3 1 1
4 2
4 1

样例输出

2.0000
IMPOSSIBLE

数据范围与提示

数据规模:对于30%的数据,n;m < = 1000;对于100%的数据,n < = 100000;m < = 10000; 1< = Ai;Bi;Ci;Si;Ti < = 10000;