共有 $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