Il y a $n$ villes. Pour chaque ville $i$, nous attribuons une valeur et payons le prix correspondant : soit la valeur est $0$ et nous payons $p_i$ pièces, soit la valeur est $1$ et nous payons $q_i$ pièces.
De plus, $m$ contraintes sont données. Une contrainte est définie par un segment $[\ell, r]$ et deux pénalités, $a$ et $b$. S'il y a au moins une ville avec la valeur $0$ parmi les villes allant de $\ell$ à $r$ inclus, nous payons une pénalité de $a$ pièces. S'il y a au moins une ville avec la valeur $1$ parmi elles, nous payons une pénalité de $b$ pièces. Les deux pénalités sont indépendantes : si $0$ et $1$ sont tous deux présents, nous payons $a + b$ pièces.
Trouvez le coût total minimal (prix plus pénalités) parmi toutes les façons de choisir des valeurs pour les villes.
Entrée
La première ligne contient un entier $t$ : le nombre de cas de test.
La première ligne de chaque cas de test contient deux entiers $n$ et $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Chacune des $n$ lignes suivantes contient deux entiers $p_i$ et $q_i$ ($1 \le p_i, q_i \le 10^9$) : les coûts respectifs du choix de $0$ et de $1$ pour la ville $i$.
Chacune des $m$ lignes suivantes contient quatre entiers $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$) : les paramètres d'une contrainte.
La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \cdot 10^5$.
La somme de $m$ sur l'ensemble des cas de test ne dépasse pas $2 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez un entier : le coût total minimal.
Exemples
Entrée 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
Sortie 1
20 8