Det finnes $n$ byer. For hver by $i$ tildeler vi en verdi og betaler prisen: enten er verdien $0$ og vi betaler $p_i$ mynter, eller så er verdien $1$ og vi betaler $q_i$ mynter.
I tillegg er det gitt $m$ betingelser. En betingelse er definert av et segment $[\ell, r]$ og to straffer, $a$ og $b$. Hvis det er minst én by med verdi $0$ blant byene fra $\ell$ til og med $r$, betaler vi en straff på $a$ mynter. Hvis det er minst én by med verdi $1$ blant dem, betaler vi en straff på $b$ mynter. De to straffene er uavhengige: hvis både $0$ og $1$ er til stede, betaler vi $a + b$ mynter.
Finn den minste totale kostnaden (priser pluss straffer) blant alle måter å velge verdier for byene på.
Inndata
Den første linjen inneholder et heltall $t$: antallet testtilfeller.
Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Hver av de neste $n$ linjene inneholder to heltall $p_i$ og $q_i$ ($1 \le p_i, q_i \le 10^9$): kostnadene for å velge henholdsvis $0$ og $1$ for by $i$.
Hver av de neste $m$ linjene inneholder fire heltall $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): parametrene til en betingelse.
Summen av $n$ over alle testtilfeller overstiger ikke $2 \cdot 10^5$.
Summen av $m$ over alle testtilfeller overstiger ikke $2 \cdot 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut ett heltall: den minste totale kostnaden.
Eksempler
Inndata 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
Utdata 1
20 8