Скидки по периодам действия тарифов

Супермаркет хранит историю скидочных тарифов отдельно от чеков. Каждый тариф относится к одному магазину и действует в некоторый промежуток времени. В чеке указаны магазин, момент оплаты и сумма покупки.

Для каждого чека нужно найти действующий в этот момент тариф его магазина. Тариф действует и в момент начала, и в момент окончания своего периода. Если подходит несколько тарифов, выбирается тариф с наибольшим временем начала действия. Если времена начала таких тарифов совпадают, выбирается тариф, который расположен раньше во входных данных.

Скидка по чеку в копейках равна сумма_чека × процент_скидки / 100. Требуется вычислить суммарную скидку по всем чекам и вывести её в рублях. Гарантируется, что для каждого чека найдётся хотя бы один подходящий тариф. Тарифы, для которых нет чеков, не влияют на ответ.

При равенстве времени начала у нескольких подходящих тарифов выбирается запись, которая раньше расположена во входных данных. Итоговая сумма округляется до копеек по правилу: значение ровно между двумя копейками округляется в большую сторону.

Формат ввода

В первой строке записаны два целых числа n и m — количество тарифов и количество чеков.

В следующих n строках записаны четыре целых числа shop_id, start_time, end_time, discount_percent — идентификатор магазина, начало и конец действия тарифа, процент скидки.

В следующих m строках записаны три целых числа shop_id, purchase_time, amount_kopecks — идентификатор магазина, момент оплаты и сумма чека в копейках.

Формат вывода

Выведите суммарную скидку в рублях с двумя знаками после точки.

Ограничения

1 ≤ n, m, n + m ≤ 4000.

1 ≤ shop_id ≤ 1000.

0 ≤ start_time ≤ end_time ≤ 10^9.

0 ≤ purchase_time ≤ 10^9.

0 ≤ discount_percent ≤ 100.

1 ≤ amount_kopecks ≤ 10^9.

Каждая строка содержит только целые числа. Для каждого чека существует хотя бы один тариф того же магазина, для которого start_time ≤ purchase_time ≤ end_time.