On $n$ kaupunkia. Jokaiselle kaupungille $i$ asetamme arvon ja maksamme hinnan: joko arvo on $0$ ja maksamme $p_i$ kolikkoa, tai arvo on $1$ ja maksamme $q_i$ kolikkoa.
Lisäksi annetaan $m$ rajoitetta. Rajoite määritellään välillä $[\ell, r]$ sekä kahdella sakolla, $a$ ja $b$. Jos kaupungeissa välillä $\ell$–$r$ (päätepisteet mukaan lukien) on vähintään yksi kaupunki, jonka arvo on $0$, maksamme $a$ kolikon sakon. Jos niiden joukossa on vähintään yksi kaupunki, jonka arvo on $1$, maksamme $b$ kolikon sakon. Nämä kaksi sakkoa ovat toisistaan riippumattomia: jos sekä $0$ että $1$ esiintyvät, maksamme $a + b$ kolikkoa.
Etsi pienin kokonaiskustannus (hinnat plus sakot) kaikkien tapojen joukosta valita arvot kaupungeille.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $t$: testitapausten lukumäärän.
Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Jokainen seuraavista $n$ rivistä sisältää kaksi kokonaislukua $p_i$ ja $q_i$ ($1 \le p_i, q_i \le 10^9$): kustannukset arvojen $0$ ja $1$ valitsemiselle kaupungille $i$, vastaavasti.
Jokainen seuraavista $m$ rivistä sisältää neljä kokonaislukua $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): rajoitteen parametrit.
Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$.
Lukujen $m$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$.
Tuloste
Tulosta jokaista testitapausta kohden yksi kokonaisluku: pienin kokonaiskustannus.
Esimerkit
Syöte 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
Tuloste 1
20 8