There are $n$ cities. For each city $i$, we assign a value and pay the price: either the value is $0$ and we pay $p_i$ coins, or the value is $1$ and we pay $q_i$ coins.
In addition, $m$ constraints are given. A constraint is defined by a segment $[\ell, r]$ and two penalties, $a$ and $b$. If there is at least one city with value $0$ among the cities from $\ell$ to $r$, inclusive, we pay a penalty of $a$ coins. If there is at least one city with value $1$ among them, we pay a penalty of $b$ coins. The two penalties are independent: if both $0$ and $1$ are present, we pay $a + b$ coins.
Find the minimum total cost (prices plus penalties) among all ways to choose values for the cities.
Input
The first line contains an integer $t$: the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Each of the next $n$ lines contains two integers $p_i$ and $q_i$ ($1 \le p_i, q_i \le 10^9$): the costs of choosing $0$ and $1$ for city $i$, respectively.
Each of the next $m$ lines contains four integers $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): the parameters of a constraint.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output one integer: the minimum total cost.
Examples
Input 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
Output 1
20 8