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.