Terdapat $n$ kota. Untuk setiap kota $i$, kita menetapkan sebuah nilai dan membayar harganya: baik nilainya adalah $0$ dan kita membayar $p_i$ koin, atau nilainya adalah $1$ dan kita membayar $q_i$ koin.
Selain itu, diberikan $m$ batasan. Sebuah batasan didefinisikan oleh segmen $[\ell, r]$ dan dua penalti, $a$ dan $b$. Jika terdapat setidaknya satu kota dengan nilai $0$ di antara kota-kota dari $\ell$ hingga $r$, inklusif, kita membayar penalti sebesar $a$ koin. Jika terdapat setidaknya satu kota dengan nilai $1$ di antaranya, kita membayar penalti sebesar $b$ koin. Kedua penalti tersebut saling independen: jika baik $0$ maupun $1$ ada, kita membayar $a + b$ koin.
Temukan total biaya minimum (harga ditambah penalti) di antara semua cara untuk memilih nilai bagi kota-kota tersebut.
Masukan
Baris pertama berisi sebuah bilangan bulat $t$: banyaknya kasus uji.
Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Masing-masing dari $n$ baris berikutnya berisi dua bilangan bulat $p_i$ dan $q_i$ ($1 \le p_i, q_i \le 10^9$): masing-masing menyatakan biaya memilih $0$ dan $1$ untuk kota $i$.
Masing-masing dari $m$ baris berikutnya berisi empat bilangan bulat $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): parameter dari sebuah batasan.
Jumlah nilai $n$ di seluruh kasus uji tidak melebihi $2 \cdot 10^5$.
Jumlah nilai $m$ di seluruh kasus uji tidak melebihi $2 \cdot 10^5$.
Keluaran
Untuk setiap kasus uji, keluarkan satu bilangan bulat: total biaya minimum.
Contoh
Masukan 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
Keluaran 1
20 8