#P3228. 超速检测勿理物理版

超速检测勿理物理版

本题在原题的基础上,去掉了物理计算超速区间的部分\red{本题在原题的基础上,去掉了物理计算超速区间的部分} 直接将超速的区间给出,并且保证给出的车辆都能被检测到\red{直接将超速的区间给出,并且保证给出的车辆都能被检测到}

题目描述

小 D 新入职了某国的交管部门,他的第一个任务是负责国家的一条长度为 LL 的南北主干道的车辆超速检测。为了考考小 D,上司首先需要他解决一个简化的场景。 这个周末,主干道上预计出现 nn 辆车超速,其中第 ii 辆车从主干道上距离最南端 lil_i 的位置开始超速,从主干道上距离最南端 rir_i 的位置停止超速。 主干道上设置了 mm 个测速仪,其中第 jj 个测速仪位于主干道上距离最南端 pjp_j 的位置,每个测速仪可以设置开启或关闭。当某辆车的超速区间(包括 lil_irir_i)内包含某个开启的测速仪时,这辆车就会被判定为超速。 上司想知道最多可以关闭多少测速仪,使每辆车仍能被判为超速。 由于 nn 很大,上司允许小 D 使用编程解决这两个问题,于是小 D 找到了你。

输入格式

输入的第一行包含一个正整数 TT,表示数据组数。

接下来包含 TT 组数据,每组数据的格式如下:

第一行包含四个整数 n,m,L,n, m, L,,分别表示超速车辆数量、测速仪数量和主干道长度。

接下来 nn 行:

ii 行包含两个整数 li,ril_i, r_i 描述一辆超速车。

最后一行包含 mm 个整数 p1,p2,,pmp_1, p_2, \dots , p_m 描述道路上所有测速仪的位置。

输出格式

对于每组数据:输出一行包含一个整数,为在不漏掉超速车辆的前提下最多可以关闭的测速仪数量。

样例 #1

样例输入 #1

1
8 10 134605
13933 27541
41957 107812
20334 127228
108114 129316
43406 134605
3891 37246
42207 129433
24555 44411
14622 27299 27606 35557 43791 48456 101617 112727 129152 129748

样例输出 #1

7

【数据范围】

对于所有测试数据,保证:

  • 1T201 \leq T \leq 20
  • 1n,m1051 \leq n, m \leq 10^51L1061 \leq L \leq 10^6
  • 0liriL0 \leq l_i \leq r_i \leq L
  • 0p1<p2<<pmL0 \leq p_1 < p_2 < \dots < p_m \leq L