Equations
Description
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
Input
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).
Output
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
Source
POJ Founder Monthly Contest – 2008.08.31, Lei, Tao