Есть $n$ городов. Каждому городу $i$ мы присваиваем значение и платим цену: либо значение равно $0$, и мы платим $p_i$ монет, либо значение равно $1$, и мы платим $q_i$ монет.
Кроме того, заданы $m$ ограничений. Ограничение определяется отрезком $[\ell, r]$ и двумя штрафами — $a$ и $b$. Если среди городов с $\ell$ по $r$ включительно есть хотя бы один город со значением $0$, мы платим штраф в размере $a$ монет. Если среди них есть хотя бы один город со значением $1$, мы платим штраф в размере $b$ монет. Эти два штрафа независимы: если присутствуют и $0$, и $1$, мы платим $a + b$ монет.
Найдите минимальную общую стоимость (цены плюс штрафы) среди всех способов выбрать значения для городов.
Входные данные
Первая строка содержит целое число $t$ — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $n$ и $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Каждая из следующих $n$ строк содержит два целых числа $p_i$ и $q_i$ ($1 \le p_i, q_i \le 10^9$) — стоимости выбора $0$ и $1$ для города $i$ соответственно.
Каждая из следующих $m$ строк содержит четыре целых числа $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$) — параметры ограничения.
Сумма $n$ по всем наборам входных данных не превосходит $2 \cdot 10^5$.
Сумма $m$ по всем наборам входных данных не превосходит $2 \cdot 10^5$.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную общую стоимость.
Примеры
Входные данные 1
2 3 2 1 5 5 1 3 3 1 3 10 10 2 2 100 1 1 1 7 8 1 1 1 1
Выходные данные 1
20 8