数轴上给出 $$$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$$$。