Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Денис — большой фанат классической музыки — не реже раза в неделю ходит на концерт в филармонию.

В этом году Денис решил закупить билетов сразу на весь сезон и даже уже выбрал список концертов, на которые хочет сходить. Теперь он думает, как именно купить эти билеты. Дело в том, что в Свердловской филармонии есть возможность выбрать любые k или более концертов и купить на них единый абонемент, стоимость которого будет равна суммарной стоимости всех входящих в него билетов со скидкой p процентов. Причём вариантов таких абонементов может быть несколько, с разными k и p. Кроме того, на некоторые концерты Денису, как студенту, полагается скидка. Но эта скидка действует только в том случае, если он покупает этот билет отдельно, вне абонемента.

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

В первой строке даны целые числа n и m — количество концертов, на которые хочет сходить Денис, и количество разных вариантов абонементов в филармонии (2 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁵). В i-й из следующих n строк записаны целые числа s_i и d_i — цена билета на i-й концерт и размер скидки студентам в процентах (100 ≤ s_i ≤ 50 000; 0 ≤ d_i ≤ 100). В j-й из следующих m строк записаны целые числа k_j и p_j — минимальное число концертов, которые можно объединить в j-й абонемент, и скидка по нему в процентах (2 ≤ k_j ≤ n; 1 ≤ p_j ≤ 100).

Выведите минимальную сумму денег, которую нужно потратить Денису, чтобы купить билеты на все выбранные им концерты. Ответ должен быть дан с абсолютной или относительной погрешностью не более 10⁻⁶.

В примере нужно купить абонемент первого типа (со скидкой 10%) на все концерты, кроме пятого, а на пятый концерт купить билет со студенческой скидкой 50%.