Є $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