$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