Universal Cup Judging System

Universal Cup

Limite de temps : 1 s Limite de mémoire : 1024 MB
Statistiques

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.