CF1830F.The Third Grace

You are given $n$ intervals and $m$ points on the number line. The $i$-th intervals covers coordinates $[l_i,r_i]$ and the $i$-th point is on coordinate $i$ and has coefficient $p_i$.

Initially, all points are not activated. You should choose a subset of the $m$ points to activate. For each of $n$ interval, we define its cost as:

• $0$, if there are no activated points in the interval;
• the coefficient of the activated point with the largest coordinate within it, otherwise.

Your task is to maximize the sum of the costs of all intervals by choosing which points to activate.

给你数轴上的 $n$ 个区间和 $m$ 个点。第 $i$ 个区间覆盖坐标范围 $[l_i,r_i]$，第 $i$ 个点位于坐标 $i$ 处，其系数为 $p_i$。

初始时，所有点均未被激活。你需要从这 $m$ 个点中选择一个子集进行激活。对每个区间（共 $n$ 个），我们定义其代价如下：

• 若该区间内没有被激活的点，则代价为 $0$；
• 否则，代价为该区间内所有被激活点中坐标最大的那个点的系数。

你的任务是通过选择合适的点进行激活，使得所有区间的代价之和最大。

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^6, 1 \le m \le 10^6$) — the number of intervals and the number of points.

The following $n$ lines of each test case contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le m$) — the endpoints of the $i$-th interval.

The following line of each test case contains $m$ integers $p_1,p_2,\ldots,p_m$ ($0 \le p_i \le 10^9$) — the coefficients of the points.

It is guaranteed that the sum of $n$ does not exceed $10^6$ and the sum of $m$ does not exceed $10^6$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $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$。

Output the maximum possible sum of costs of all intervals.

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

In the first sample, we can activate points $1$ and $8$. The sum of costs of all intervals will be $78+30=108$.

In the second sample, we will activate no points. The sum of costs of all intervals will be $0$.

在第一个样例中，我们可以激活点 $1$ 和 $8$。所有区间的成本之和为 $78+30=108$。

在第二个样例中，我们将不激活任何点。所有区间的成本之和为 $0$。