Hay $n$ ciudades. Para cada ciudad $i$, asignamos un valor y pagamos el precio: o bien el valor es $0$ y pagamos $p_i$ monedas, o bien el valor es $1$ y pagamos $q_i$ monedas.
Además, se dan $m$ restricciones. Una restricción se define mediante un segmento $[\ell, r]$ y dos penalizaciones, $a$ y $b$. Si hay al menos una ciudad con valor $0$ entre las ciudades desde $\ell$ hasta $r$, inclusive, pagamos una penalización de $a$ monedas. Si hay al menos una ciudad con valor $1$ entre ellas, pagamos una penalización de $b$ monedas. Las dos penalizaciones son independientes: si tanto $0$ como $1$ están presentes, pagamos $a + b$ monedas.
Encuentre el costo total mínimo (precios más penalizaciones) entre todas las formas de elegir valores para las ciudades.
Entrada
La primera línea contiene un entero $t$: el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ($1 \le n, m \le 2 \cdot 10^5$).
Cada una de las siguientes $n$ líneas contiene dos enteros $p_i$ y $q_i$ ($1 \le p_i, q_i \le 10^9$): los costos de elegir $0$ y $1$ para la ciudad $i$, respectivamente.
Cada una de las siguientes $m$ líneas contiene cuatro enteros $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): los parámetros de una restricción.
La suma de $n$ en todos los casos de prueba no supera $2 \cdot 10^5$.
La suma de $m$ en todos los casos de prueba no supera $2 \cdot 10^5$.
Salida
Para cada caso de prueba, imprima un entero: el costo total mínimo.
Ejemplos
Entrada 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
Salida 1
20 8