C. Грибные гномы - 2
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Гуляя как-то раз по лесу, Наташа встретила маленького грибного гномика. Гномик рассказал ей следующую историю:

Как известно, сила грибных гномов заключена в волшебных грибах, которые растут в их родном лесу. В этом лесу растет n деревьев и m волшебных грибов: i-ое дерево растет в точке на прямой с координатой ai и имеет высоту hi, j-ый гриб растет в точке с координатой bj и имеет волшебную силу zj.

Но однажды заклятые враги грибных гномов — дикие грибожуи — наслали на их родной лес ужасный шторм, в результате которого некоторые деревья начали падать и давить волшебные грибы. Верховный оракул грибных гномов заранее посчитал для каждого дерева вероятность того, что дерево упадет влево, вправо или останется стоять. Если дерево с координатой x и высотой h падает влево, то все грибы, попадающие в полуинтервал [x - h, x), погибают; если дерево падает вправо, погибают грибы в полуинтервале (x, x + h]. Выживают лишь те грибы, на которые не упадет ни одного дерева.

Зная, что все деревья падают независимо друг от друга (т.е. всевозможные события относительно различных деревьев взаимно независимы, и, кроме того, деревья никак не мешают другим деревьям падать в произвольном направлении), верховный оракул также смог быстро посчитать, каково будет матожидание суммарной силы выживших после шторма грибов, что в итоге спасло грибных гномов от неминуемой гибели.

Наташу, как неплохого олимпиадного программиста, заинтересовала эта история, и она решила придумать, как же можно быстро посчитать матожидание суммы сил выживших грибов.

Входные данные

В первой строке находится два целых числа n и m (1 ≤ n ≤ 105, 1 ≤ m ≤ 104) — количество деревьев и грибов соответственно.

В следующих n строках находится по четыре целых числа — ai, hi, li, ri (|ai| ≤ 109, 1 ≤ hi ≤ 109, 0 ≤ li, ri, li + ri ≤ 100)  — координата i-го дерева, его высота, вероятность (в процентах) его падения влево и вправо соответственно (с оставшейся вероятностью дерево остается стоять).

В следующих m строках находится по два целых числа — bj, zj (|bj| ≤ 109, 1 ≤ zj ≤ 103) — координата и волшебная сила j-ого гриба соответственно.

Произвольное число деревьев и грибов могут расти в одной точке.

Выходные данные

Выведите одно вещественное число — матожидание суммарной волшебной силы выживших грибов. Ответ принимается с относительной или абсолютной точностью 10 - 4.

Примеры
Входные данные
1 1
2 2 50 50
1 1
Выходные данные
0.5000000000
Входные данные
2 1
2 2 50 50
4 2 50 50
3 1
Выходные данные
0.2500000000
Примечание

Считается, что гриб с координатой x попадает в полуинтервал [l, r) тогда и только тогда, когда l ≤ x < r. Аналогично, гриб с координатой x попадает в полуинтервал (l, r] тогда и только тогда, когда l < x ≤ r.

В первом тесте гриб выживает с вероятностью 50% в зависимости от того, куда упадет единственное дерево.

Во втором тесте гриб выживает только тогда, когда на него не упадет ни одно из двух деревьев, что происходит с вероятностью 50%  ×  50% = 25%.

Претест №12 — большой тест с 105 деревьями и одним грибом.