Universal Cup Judging System

Universal Cup

حد الوقت: 1 s حد الذاكرة: 1024 MB
الإحصائيات

$n$개의 도시가 있습니다. 각 도시 $i$에 대해 값을 배정하고 가격을 지불합니다. 값이 $0$이면 $p_i$ 코인을 지불하고, 값이 $1$이면 $q_i$ 코인을 지불합니다.

추가로 $m$개의 제약 조건이 주어집니다. 각 제약 조건은 구간 $[\ell, r]$과 두 벌금 $a$, $b$로 정의됩니다. $\ell$부터 $r$까지(양 끝 포함)의 도시 중 값이 $0$인 도시가 적어도 하나 있으면 벌금으로 $a$ 코인을 지불합니다. 그중 값이 $1$인 도시가 적어도 하나 있으면 벌금으로 $b$ 코인을 지불합니다. 두 벌금은 서로 독립적입니다. 만약 $0$과 $1$이 모두 존재하면 $a + b$ 코인을 지불합니다.

도시들의 값을 정하는 모든 방법 중에서 최소 총비용(가격과 벌금의 합)을 구하십시오.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $t$가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 2 \cdot 10^5$)이 주어집니다.

다음 $n$개의 줄에는 각각 두 정수 $p_i$와 $q_i$ ($1 \le p_i, q_i \le 10^9$)가 주어집니다. 이는 각각 도시 $i$에 대해 $0$과 $1$을 선택하는 비용입니다.

다음 $m$개의 줄에는 각각 네 정수 $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$)가 주어집니다. 이는 제약 조건의 매개변수입니다.

모든 테스트 케이스에 대한 $n$의 합은 $2 \cdot 10^5$을 초과하지 않습니다.

모든 테스트 케이스에 대한 $m$의 합은 $2 \cdot 10^5$을 초과하지 않습니다.

출력

각 테스트 케이스마다 최소 총비용을 나타내는 정수 하나를 출력합니다.

예제

입력 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

출력 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.