Det finns $n$ städer. För varje stad $i$ tilldelar vi ett värde och betalar priset: antingen är värdet $0$ och vi betalar $p_i$ mynt, eller så är värdet $1$ och vi betalar $q_i$ mynt.
Dessutom ges $m$ villkor. Ett villkor definieras av ett segment $[\ell, r]$ och två straffavgifter, $a$ och $b$. Om det finns minst en stad med värdet $0$ bland städerna från $\ell$ till $r$, inklusive ändpunkterna, betalar vi en straffavgift på $a$ mynt. Om det finns minst en stad med värdet $1$ bland dem betalar vi en straffavgift på $b$ mynt. De två straffavgifterna är oberoende av varandra: om både $0$ och $1$ förekommer betalar vi $a + b$ mynt.
Hitta den minsta totalkostnaden (priser plus straffavgifter) bland alla sätt att välja värden för städerna.
Indata
Den första raden innehåller ett heltal $t$: antalet testfall.
Den första raden i varje testfall innehåller två heltal $n$ och $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Var och en av de följande $n$ raderna innehåller två heltal $p_i$ och $q_i$ ($1 \le p_i, q_i \le 10^9$): kostnaderna för att välja $0$ respektive $1$ för stad $i$.
Var och en av de följande $m$ raderna innehåller fyra heltal $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): parametrarna för ett villkor.
Summan av $n$ över alla testfall överstiger inte $2 \cdot 10^5$.
Summan av $m$ över alla testfall överstiger inte $2 \cdot 10^5$.
Utdata
För varje testfall, skriv ut ett heltal: den minsta totalkostnaden.
Exempel
Indata 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