OpenJudge

7:Equations

总时间限制:
1000ms
内存限制:
65536kB
描述

Given 3 × n positive integers:

A1,     A2,     A3,     ...     An;
B1,     B2,     B3,     ...     Bn;
C1,     C2,      C3,     ...     Cn;

and a set of m pairs of integer < Si, Ti >, your task is to find a non-negative real solution for the following equations:

A1X1 + A2X2 + A3X3 + ... + AnXn = Si
B1X1 + B2X2 + B3X3 + ... + BnXn = Ti

that maximizes C1X1 + C2X2 + C3X3 + ... + CnXn

输入

The first line contains two numbers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 10000).
The following n lines each contain three integers Ai, Bi, Ci (1 ≤ Ai, Bi, Ci ≤ 10000). The next m lines each contain two integers Si and Ti (1 ≤ Si, Ti ≤ 10000).

输出

For each pair < Si, Ti >, output the maximum value or IMPOSSIBLE if no solution exists.

样例输入
2 2
2 2 2
3 1 1
4 2
4 1
样例输出
2.00000
IMPOSSIBLE
全局题号
2854
添加于
2015-08-18
提交次数
0
尝试人数
0
通过人数
0