题目描述

给出 $3$ 个长度均为 $n$ 的正整数序列 $A,B,C$；以及 $m$ 对整数，你的目标是找到一组非负实数解满足如下方程组： $\sum^n_{i=1}A_iX_i = S_i$ $\sum^n_{i=1}B_iX_i = T_i$ 并且使得 $\sum^n_{i=1}C_iX_i$ 的值最大。

输入格式

第一行包含两个整数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；

题目来源

Spj程序 By Dzy