總共有 $n$ 個城市。對於每個城市 $i$,我哋會為佢分配一個數值並畀相應嘅價錢:一係數值係 $0$ 並畀 $p_i$ 個銀仔,一係數值係 $1$ 並畀 $q_i$ 個銀仔。
另外,俾定 $m$ 個限制條件。每個限制條件由一個區間 $[\ell, r]$ 同埋兩個罰金 $a$ 同 $b$ 定義。如果由 $\ell$ 到 $r$(包埋頭尾)嘅城市入面最少有一個城市嘅數值係 $0$,我哋就要畀 $a$ 個銀仔嘅罰金。如果入面最少有一個城市嘅數值係 $1$,我哋就要畀 $b$ 個銀仔嘅罰金。呢兩個罰金係互相獨立嘅:如果 $0$ 同 $1$ 同時存在,我哋就要畀 $a + b$ 個銀仔。
喺所有為城市揀數值嘅方案入面,求最小嘅總花費(價錢加埋罰金)。
輸入格式
第一行包含一個整數 $t$:測試資料嘅數量。
每組測試資料嘅第一行包含兩個整數 $n$ 同 $m$($1 \le n, m \le 2 \cdot 10^5$)。
接落嚟 $n$ 行入面嘅每一行包含兩個整數 $p_i$ 同 $q_i$($1 \le p_i, q_i \le 10^9$):分別係為城市 $i$ 揀 $0$ 同 $1$ 嘅花費。
接落嚟 $m$ 行入面嘅每一行包含四個整數 $\ell$、$r$、$a$、$b$($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$):一個限制條件嘅參數。
所有測試資料入面 $n$ 嘅總和唔超過 $2 \cdot 10^5$。
所有測試資料入面 $m$ 嘅總和唔超過 $2 \cdot 10^5$。
輸出格式
對於每組測試資料,輸出一個整數:最小嘅總花費。
樣例
輸入格式 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
輸出格式 1
20 8