- Time limit: 1.00 s
- Memory limit: 512 MB
Teemu takes a course in Computational Simulation of Everyday World. Teemu has decided to model a storm in a nearby forest which is used for mushroom harvesting.
The forest has t trees and m mushrooms on a single line. Each tree resides at a position a_i on the line and has a height h_i. Each mushroom has a position b_j and value v_j.
Teemu knows that each tree i has a chance l_i percentages of falling left and a chance r_i percentages of falling right. The rest of the time it doesn't fall. When a tree i falls left, it will crush and destroy all mushrooms on half open interval [a_i-h_i, a_i[. When a tree falls left, it will crush and destroy all mushrooms on half open interval ]a_i, a_i+h_i].
Input
The first line consists of two integers, t and m, the number of trees and the number of mushrooms in the forest, respectively.
Next t lines each consists of four integers, a_i, h_i, l_i and r_i, the position of the tree i, its height, chance of falling left and chance of falling right, respectively.
Next m lines each consists of two integers, b_j and v_j, the position of the j^{th} mushroom and its value, respectively.
Output
A single real number, the expected value of all non-crushed mushrooms in the forest. The result is accepted with relative or absolute accuracy 10^{-4}.
Limits
- 1 \le t \le 10^5
- 1 \le m \le 10^4
- |a_i|, |b_i| \le 10^9
- 1 \le v_i \le 10^3
- 1 \le h_i \le 10^9
- 0 \le l_i, r_i, l_i+r_i \le 100
Example
Input:
1 1 2 2 50 50 1 1
Output:
0.5
Input:
2 1 2 2 50 50 4 2 50 50 3 1
Output:
0.25
Original task: http://codeforces.com/contest/138/problem/C