第三位缪斯

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

数轴上有 $n$ 个区间和 $m$ 个点。第 $i$ 个区间覆盖坐标 $[l_i,r_i]$；第 $i$ 个点位于坐标 $i$，权值为 $p_i$。

最初所有点均未激活。一个区间的代价按照以下规则定义：

• 若区间内没有激活点，代价为 $0$；
• 否则，代价等于区间内坐标最大的激活点的权值。

你可以任选若干个点激活，也可以一个点都不激活。求所有区间代价之和的最大值。

输入格式

第一行一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行两个整数 $n,m$；
• 接下来 $n$ 行，每行两个整数 $l_i,r_i$，表示一个区间；
• 接下来一行 $m$ 个整数 $p_1,p_2,\ldots,p_m$，表示各点权值。

输出格式

对于每组测试数据，输出一行一个整数，表示所有区间代价之和的最大值。

样例输入 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$。

数据范围

对于全部数据，$1\le t\le10^5$，$1\le n,m\le10^6$，$1\le l_i\le r_i\le m$，$0\le p_i\le10^9$。所有测试数据的 $n$ 之和不超过 $10^6$，$m$ 之和不超过 $10^6$。

每个测试点独立计分。