D. 鲨鱼冲浪

每次测试时间限制：3 秒
内存限制：256 兆字节

Mualani 喜欢在她的鲨鱼冲浪板上冲浪！

Mualani 的冲浪路径可以建模为一个数轴。她从位置 $1$ 出发，终点在位置 $L$。当她位于位置 $x$，且跳跃能力为 $k$ 时，她可以跳到区间 $[x, x + k]$ 内的任意整数位置。初始时，她的跳跃能力为 $1$。

然而，冲浪路径并非完全平坦。路上有 $n$ 个障碍物，每个障碍物用一个区间 $[l, r]$ 表示，意味着她不能跳到区间 $[l, r]$ 内的任何位置。

路上还有 $m$ 个强化道具，位于某些位置。第 $i$ 个强化道具位于位置 $x_i$，数值为 $v_i$。当 Mualani 到达位置 $x_i$ 时，她可以选择拾取该道具，使自己的跳跃能力增加 $v_i$。同一个位置可能有多个强化道具。当她在某个有强化道具的位置时，可以独立选择拾取或不拾取每个道具。没有强化道具位于任何障碍物的区间内。

为了到达终点 $L$，她必须至少收集多少个强化道具？如果无法完成冲浪路径，输出 $-1$。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$、$L$（$1 \le n, m \le 2 \cdot 10^5$，$3 \le L \le 10^9$）——障碍物数量、强化道具数量、终点的位置。

接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$2 \le l_i \le r_i \le L-1$）——第 $i$ 个障碍物的区间边界。保证对于所有 $1 \le i < n$，满足 $r_i + 1 < l_{i+1}$（即障碍物互不重叠，按位置升序排列，且前一个障碍物的终点与下一个障碍物的起点不连续）。

接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $v_i$（$1 \le x_i, v_i \le L$）——第 $i$ 个强化道具的位置和数值。同一个 $x$ 可能有多个道具。保证对于所有 $1 \le i < m$，满足 $x_i \le x_{i+1}$（即道具按位置非递减排序），且没有强化道具位于任何障碍物的区间内。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出她必须收集的最少强化道具数量。如果无法到达终点 $L$，输出 $-1$。

示例

输入：

4
2 5 50
7 14
30 40
2 2
3 1
3 5
18 2
22 32
4 3 50
4 6
15 18
20 26
34 38
1 2
8 2
10 2
1 4 17
10 14
1 6
1 2
1 2
16 9
1 2 10
5 9
2 3
2 2

输出：

4
-1
1
2

说明

• 在第一个测试用例中，她可以收集第 $1$、$2$、$3$、$5$ 个强化道具，从而越过所有障碍物。
• 在第二个测试用例中，她无法跳过第一个障碍物。
• 在第四个测试用例中，通过收集两个强化道具，她可以越过障碍物。