$n$ 個の都市があります。各都市 $i$ に対して値を割り当て、代金を支払います。値が $0$ の場合は $p_i$ コインを支払い、値が $1$ の場合は $q_i$ コインを支払います。
さらに、$m$ 個の制約が与えられます。各制約は区間 $[\ell, r]$ と 2 つのペナルティ $a$, $b$ によって定義されます。都市 $\ell$ から都市 $r$ まで(両端を含む)の都市の中に値が $0$ の都市が少なくとも 1 つ存在する場合、ペナルティとして $a$ コインを支払います。その中に値が $1$ の都市が少なくとも 1 つ存在する場合、ペナルティとして $b$ コインを支払います。これら 2 つのペナルティは独立しており、$0$ と $1$ の両方が存在する場合は $a + b$ コインを支払います。
都市に値を割り当てるすべての方法の中で、総コスト(代金とペナルティの合計)の最小値を求めてください。
入力
1 行目には整数 $t$ が与えられます。これはテストケースの数です。
各テストケースの 1 行目には、2 つの整数 $n$ と $m$($1 \le n, m \le 2 \cdot 10^5$)が与えられます。
続く $n$ 行のそれぞれには、2 つの整数 $p_i$ と $q_i$($1 \le p_i, q_i \le 10^9$)が与えられます。これらはそれぞれ都市 $i$ に対して $0$ と $1$ を選ぶ際のコストです。
続く $m$ 行のそれぞれには、4 つの整数 $\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 つ出力してください。
入出力例
入力 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