Það eru $n$ borgir. Fyrir hverja borg $i$ úthlutum við gildi og greiðum verðið: annaðhvort er gildið $0$ og við greiðum $p_i$ myntir, eða gildið er $1$ og við greiðum $q_i$ myntir.
Að auki eru gefin $m$ skilyrði. Skilyrði er skilgreint með bili $[\ell, r]$ og tveimur sektum, $a$ og $b$. Ef það er að minnsta kosti ein borg með gildið $0$ meðal borganna frá $\ell$ til $r$, báðum meðtöldum, greiðum við sekt upp á $a$ myntir. Ef það er að minnsta kosti ein borg með gildið $1$ á meðal þeirra greiðum við sekt upp á $b$ myntir. Sektirnar tvær eru óháðar: ef bæði $0$ og $1$ eru til staðar greiðum við $a + b$ myntir.
Finnið lágmarks heildarkostnað (verð plús sektir) meðal allra leiða til að velja gildi fyrir borgirnar.
Inntak
Fyrsta línan inniheldur heiltölu $t$: fjölda prófunartilfella.
Fyrsta línan í hverju prófunartilfelli inniheldur tvær heiltölur $n$ og $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Hver af næstu $n$ línum inniheldur tvær heiltölur $p_i$ og $q_i$ ($1 \le p_i, q_i \le 10^9$): kostnaðinn við að velja $0$ annars vegar og $1$ hins vegar fyrir borg $i$.
Hver af næstu $m$ línum inniheldur fjórar heiltölur $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): stika skilyrðis.
Summa $n$ yfir öll prófunartilfelli fer ekki yfir $2 \cdot 10^5$.
Summa $m$ yfir öll prófunartilfelli fer ekki yfir $2 \cdot 10^5$.
Úttak
Fyrir hvert prófunartilfelli skal prenta eina heiltölu: lágmarks heildarkostnað.
Dæmi
Inntak 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
Úttak 1
20 8