Ci sono $n$ città. Per ogni città $i$, assegniamo un valore e paghiamo il prezzo corrispondente: o il valore è $0$ e paghiamo $p_i$ monete, oppure il valore è $1$ e paghiamo $q_i$ monete.
Inoltre, vengono dati $m$ vincoli. Un vincolo è definito da un segmento $[\ell, r]$ e da due penalità, $a$ e $b$. Se c'è almeno una città con valore $0$ tra le città da $\ell$ a $r$, estremi inclusi, paghiamo una penalità di $a$ monete. Se c'è almeno una città con valore $1$ tra di esse, paghiamo una penalità di $b$ monete. Le due penalità sono indipendenti: se sono presenti sia $0$ che $1$, paghiamo $a + b$ monete.
Trova il costo totale minimo (prezzi più penalità) tra tutti i modi possibili di scegliere i valori per le città.
Input
La prima riga contiene un intero $t$: il numero di casi di test.
La prima riga di ogni caso di test contiene due interi $n$ e $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Ciascuna delle successive $n$ righe contiene due interi $p_i$ e $q_i$ ($1 \le p_i, q_i \le 10^9$): rispettivamente i costi per scegliere $0$ e $1$ per la città $i$.
Ciascuna delle successive $m$ righe contiene quattro interi $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): i parametri di un vincolo.
La somma di $n$ su tutti i casi di test non supera $2 \cdot 10^5$.
La somma di $m$ su tutti i casi di test non supera $2 \cdot 10^5$.
Output
Per ogni caso di test, stampa un intero: il costo totale minimo.
Esempi
Input 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
Output 1
20 8