310420: CF1830F. The Third Grace

F. The Third Gracetime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

Output the maximum possible sum of costs of all intervals.

ExampleInput

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

Output

108
0

Note

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$.

题目大意：
题目描述了一个在数轴上选择点的问题。你有一系列的区间和点，每个区间由两个端点定义，每个点有一个坐标和一个系数。最初所有的点都是未激活的，你的任务是选择一些点来激活，以使得所有区间的成本之和最大。一个区间的成本定义为：如果区间内没有激活的点，则成本为0；如果有激活的点，则成本是区间内坐标最大的激活点的系数。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^5），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m（1 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^6），分别表示区间的数量和点的数量。
- 接下来的n行，每行包含两个整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ m），表示第i个区间的端点。
- 紧接着的一行包含m个整数p_1,p_2,…,p_m（0 ≤ p_i ≤ 10^9），表示每个点的系数。

输出：
- 对于每个测试用例，输出一个整数，表示通过激活点可以获得的最大区间成本之和。

示例输入输出：
输入：
```
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
```
输出：
```
108
0
```

注意：
- 在第一个示例中，激活点1和点8，区间成本之和为78+30=108。
- 在第二个示例中，不激活任何点，区间成本之和为0。题目大意： 题目描述了一个在数轴上选择点的问题。你有一系列的区间和点，每个区间由两个端点定义，每个点有一个坐标和一个系数。最初所有的点都是未激活的，你的任务是选择一些点来激活，以使得所有区间的成本之和最大。一个区间的成本定义为：如果区间内没有激活的点，则成本为0；如果有激活的点，则成本是区间内坐标最大的激活点的系数。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^5），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和m（1 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^6），分别表示区间的数量和点的数量。 - 接下来的n行，每行包含两个整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ m），表示第i个区间的端点。 - 紧接着的一行包含m个整数p_1,p_2,…,p_m（0 ≤ p_i ≤ 10^9），表示每个点的系数。 输出： - 对于每个测试用例，输出一个整数，表示通过激活点可以获得的最大区间成本之和。 示例输入输出： 输入： ``` 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 ``` 输出： ``` 108 0 ``` 注意： - 在第一个示例中，激活点1和点8，区间成本之和为78+30=108。 - 在第二个示例中，不激活任何点，区间成本之和为0。