Universal Cup Judging System

Universal Cup

Süre Sınırı: 1 s Bellek Sınırı: 1024 MB
İstatistikler

Danych jest $n$ miast. Każdemu miastu $i$ przypisujemy wartość i płacimy cenę: albo wartość wynosi $0$ i płacimy $p_i$ monet, albo wartość wynosi $1$ i płacimy $q_i$ monet.

Ponadto danych jest $m$ ograniczeń. Ograniczenie jest zdefiniowane przez przedział $[\ell, r]$ oraz dwie kary, $a$ i $b$. Jeśli wśród miast od $\ell$ do $r$ włącznie istnieje co najmniej jedno miasto o wartości $0$, płacimy karę w wysokości $a$ monet. Jeśli wśród nich istnieje co najmniej jedno miasto o wartości $1$, płacimy karę w wysokości $b$ monet. Obie kary są niezależne: jeśli występują zarówno $0$, jak i $1$, płacimy $a + b$ monet.

Znajdź minimalny łączny koszt (ceny plus kary) spośród wszystkich sposobów wyboru wartości dla miast.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $t$: liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 2 \cdot 10^5$).

Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $p_i$ oraz $q_i$ ($1 \le p_i, q_i \le 10^9$): odpowiednio koszty wyboru $0$ i $1$ dla miasta $i$.

Każdy z kolejnych $m$ wierszy zawiera cztery liczby całkowite $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): parametry ograniczenia.

Suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Suma wartości $m$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: minimalny łączny koszt.

Przykład

Wejście 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

Wyjście 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.