解题思路

将每条内容看成一个可匹配区间 $[l_i,r_i]$，每个推荐位看成一个热度值 $s_j$。问题就是：每个点 $s_j$ 最多匹配一个区间，每个区间最多被匹配一次，求最多匹配数量。

使用贪心算法 + 排序 + 小根堆。

核心思路：

按 $l_i$ 从小到大排序所有区间，按热度值 $s_j$ 从小到大排序所有推荐位。

题目内容

多多正在为首页内容安排推荐位。一共有 $m$ 个推荐位，第 $j$ 个推荐位的热度值为 $s_j$。

同时有 $n$ 条内容需要参与分发。对于第 $i$ 条内容，多多已经评估出一个可接受的推荐位热度范围 $[l_i, r_i]$：

• 如果推荐位热度值小于 $l_i$，曝光不足；
• 如果推荐位热度值大于 $r_i$，则和这条内容不够匹配。

因此，第 $i$ 条内容只能放到热度值属于 $[l_i, r_i]$ 的推荐位上。

每个推荐位最多放置一条内容，每条内容也最多放置到一个推荐位。请你帮助多多计算：最多可以成功匹配多少条内容。

输入描述

第一行输入一个整数 $T(1 \le T \le 3)$，表示数据组数。 接下来对于每组数据：

• 第一行输入两个整数 $n(1 \le n \le 2 \times 10^5)$ 和 $m(1 \le m \le 2 \times 10^5)$。
• 接下来 $n$ 行，每行输入两个整数 $l_i, r_i(0 \le l_i \le r_i \le 10^9)$。
• 最后一行输入 $m$ 个整数 $s_1, s_2, \dots, s_m(0 \le s_j \le 10^9)$。

输出描述

对于每组数据，仅输出一行整数，表示最多能够匹配的内容数量。

样例1

输入

1
4 4
1 2
2 2
2 3
4 5
2 3 5 6

输出

3

说明

一种最优匹配方式为：

• 热度值为 $2$ 的推荐位分配给区间 $[2, 2]$
• 热度值为 $3$ 的推荐位分配给区间 $[2, 3]$
• 热度值为 $5$ 的推荐位分配给区间 $[4, 5]$

因此最多可以匹配 $3$ 条内容。