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