3689 -- Equations

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Language:

Equations

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1551		Accepted: 145

Description

Given 3 × n positive integers:

A₁, A₂, A₃, ... A_n;
B₁, B₂, B₃, ... B_n;
C₁, C₂, C₃, ... C_n;

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

A₁X₁ + A₂X₂ + A₃X₃ + ... + A_nX_n = S_i
B₁X₁ + B₂X₂ + B₃X₃ + ... + B_nX_n = T_i

that maximizes C₁X₁ + C₂X₂ + C₃X₃ + ... + C_nX_n

Input

The first line contains two numbers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 10000).
The following n lines each contain three integers A_i, B_i, C_i (1 ≤ A_i, B_i, C_i ≤ 10000). The next m lines each contain two integers S_i and T_i (1 ≤ S_i, T_i ≤ 10000).

Output

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

Sample Input

Sample Output

2.00000
IMPOSSIBLE

Source

POJ Founder Monthly Contest – 2008.08.31, Lei, Tao

[Submit] [Go Back] [Status] [Discuss]

Home Page Go Back To top