Danych jest $n$ miast. Każdemu miastu $i$ przypisujemy wartość i płacimy cenę: albo wartość wynosi $0$ i płacimy $p_i$ monet, albo wartość wynosi $1$ i płacimy $q_i$ monet.
Ponadto danych jest $m$ ograniczeń. Ograniczenie jest zdefiniowane przez przedział $[\ell, r]$ oraz dwie kary, $a$ i $b$. Jeśli wśród miast od $\ell$ do $r$ włącznie istnieje co najmniej jedno miasto o wartości $0$, płacimy karę w wysokości $a$ monet. Jeśli wśród nich istnieje co najmniej jedno miasto o wartości $1$, płacimy karę w wysokości $b$ monet. Obie kary są niezależne: jeśli występują zarówno $0$, jak i $1$, płacimy $a + b$ monet.
Znajdź minimalny łączny koszt (ceny plus kary) spośród wszystkich sposobów wyboru wartości dla miast.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $t$: liczbę przypadków testowych.
Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $p_i$ oraz $q_i$ ($1 \le p_i, q_i \le 10^9$): odpowiednio koszty wyboru $0$ i $1$ dla miasta $i$.
Każdy z kolejnych $m$ wierszy zawiera cztery liczby całkowite $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): parametry ograniczenia.
Suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.
Suma wartości $m$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: minimalny łączny koszt.
Przykład
Wejście 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
Wyjście 1
20 8