There's only three weeks left until Christmas and Santa is in big trouble: all his elves have gone on strike! Furthermore, the toy-making machines are deteriorating at an alarming rate.
Santa has machines. Each machine can produce toys at a rate given by , where and are constants unique to the machine and is the time. The machines stop working once they reach a negative rate (at time ). Santa may only operate one machine at a time, but with his magical abilities, he can switch between machines instantly.
Santa wants to know if he can finish making all the toys on time, so he has asked you, his only remaining helper, to answer queries: the number of toys he can produce from time to time .
Note: A machine with constants and can produce toys from time to .
Input
The first line contains two integers, \(M, Q\).
The next lines each contain two numbers, describing the machine.
The next lines each contain two integers, describing a query.
Input Constraints
\(1 \le M, Q \le 100\)
\(0 \le a \le 1\) \(000, a \in \mathbb{R}\)
\(1 < b \le 10^6\)
\(0 \le x < y \le 10^5\)
For of the points, \(M = 2\).
Output
For each query, output the maximum number of toys that Santa can produce in the
given interval of time.
Your answer will be counted as correct if it is within a relative or absolute error of from the judge's answer.
Sample Input 1
2 3
2 4
1 3
0 1
1 3
0 4
Sample Output 1
3.000
2.000
5.000
Explanation for Sample Output 1
For the first query, it is optimal to use the first machine for the entire interval. For the second, it is optimal to use the second machine for the entire interval. For the third query, use the first machine for the first minute, and the second machine for the next two minutes, and past the third minute, all machines are broken.
Sample Input 2
4 5
2 10
1 7.5
0.5 5
1 6.5
0 1
0 2
0 4
1 2
0 10
Sample Output 2
9.000
16.000
25.125
7.000
34.375
Comments
Test data for this problem has been [finally] uploaded. :D