Es gibt $n$ Städte. Für jede Stadt $i$ weisen wir einen Wert zu und zahlen den Preis: Entweder ist der Wert $0$ und wir zahlen $p_i$ Münzen, oder der Wert ist $1$ und wir zahlen $q_i$ Münzen.
Zusätzlich sind $m$ Bedingungen gegeben. Eine Bedingung wird durch ein Segment $[\ell, r]$ und zwei Strafen $a$ und $b$ definiert. Wenn es unter den Städten von $\ell$ bis einschließlich $r$ mindestens eine Stadt mit dem Wert $0$ gibt, zahlen wir eine Strafe von $a$ Münzen. Wenn es unter ihnen mindestens eine Stadt mit dem Wert $1$ gibt, zahlen wir eine Strafe von $b$ Münzen. Die beiden Strafen sind voneinander unabhängig: Wenn sowohl $0$ als auch $1$ vorkommen, zahlen wir $a + b$ Münzen.
Finden Sie die minimalen Gesamtkosten (Preise plus Strafen) unter allen Möglichkeiten, Werte für die Städte zu wählen.
Eingabe
Die erste Zeile enthält eine ganze Zahl $t$: die Anzahl der Testfälle.
Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Jede der nächsten $n$ Zeilen enthält zwei ganze Zahlen $p_i$ und $q_i$ ($1 \le p_i, q_i \le 10^9$): die Kosten für die Wahl von $0$ bzw. $1$ für Stadt $i$.
Jede der nächsten $m$ Zeilen enthält vier ganze Zahlen $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): die Parameter einer Bedingung.
Die Summe von $n$ über alle Testfälle hinweg überschreitet nicht $2 \cdot 10^5$.
Die Summe von $m$ über alle Testfälle hinweg überschreitet nicht $2 \cdot 10^5$.
Ausgabe
Geben Sie für jeden Testfall eine ganze Zahl aus: die minimalen Gesamtkosten.
Beispiele
Eingabe 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
Ausgabe 1
20 8