Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Equations
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1092Accepted: 104

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.

Sample Input

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

Sample Output

2.00000
IMPOSSIBLE

Source

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

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator