← 返回题目列表

Codeforces · 1830/F

F. 第三恩典

中文机器翻译题面 查看原题

数轴上给出 $$$n$$$ 区间和 $$$m$$$ 点。第 $$$i$$$ 个区间覆盖坐标 $$$[l_i,r_i]$$$,第 $$$i$$$ 个点位于坐标 $$$i$$$ 上,并具有系数 $$$p_i$$$。

最初,所有点均未激活。您应该选择 $$$m$$$ 点的子集来激活。对于每个 $$$n$$$ 区间,我们将其成本定义为:

- $$$0$$$,如果区间内没有激活点;
- 激活点内坐标最大的系数,否则。

您的任务是通过选择要激活的点来最大化所有间隔的成本总和。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6, 1 \le m \le 10^6$$$) - 间隔数和点数。

每个测试用例的以下 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) - 第 $$$i$$$ 个区间的端点。

每个测试用例的以下行包含 $$$m$$$ 整数 $$$p_1,p_2,\ldots,p_m$$$ ($$$0 \le p_i \le 10^9$$$) — 点的系数。

保证$$$n$$$的总和不超过$$$10^6$$$,$$$m$$$的总和不超过$$$10^6$$$。

输出

输出所有区间的最大可能成本总和。

示例

输入 #1

2
2 8
1 5
3 8
78 0 50 0 0 0 0 30
1 6
1 5
0 0 0 0 0 100

输出 #1

108
0

注意

在第一个示例中,我们可以激活点 $$$1$$$ 和 $$$8$$$。所有间隔的成本总和将为$$$78+30=108$$$。

在第二个示例中,我们将不激活任何点。所有时间间隔的成本总和将为 $$$0$$$。