CF2037D Sharky Surfing

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$。在同一个位置可能有多个能量提升点。当她处于有多个能量提升点的位置时，她可以选择收集或忽略每个单独的能量提升点。没有能量提升点位于任何障碍物的区间内。 Mualani 必须收集最少的能量提升点数才能到达位置 $L$ 完成冲浪路径。如果无法完成冲浪路径，则输出 $-1$。

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。 每个测试用例的第一行包含三个整数 $n$, $m$, 和 $L$ ($1 \leq n, m \leq 2 \cdot 10^5, 3 \leq L \leq 10^9$) — 障碍物的数量，能量提升点的数量，以及终点的位置。 接下来的 $n$ 行每行包含两个整数 $l_i$ 和 $r_i$ ($2 \leq l_i \leq r_i \leq L-1$) — 第 $i$ 个障碍物的区间边界。保证对于所有 $1 \leq i < n$，有 $r_i + 1 < l_{i+1}$（即所有障碍物都是非重叠的，按递增位置排序，并且前一个障碍物的终点与下一个障碍物的起点不连续）。 接下来的 $m$ 行每行包含两个整数 $x_i$ 和 $v_i$ ($1 \leq x_i, v_i \leq L$) — 第 $i$ 个能量提升点的位置和值。在所有测试用例中，能量提升点的数量总和不超过 $2 \cdot 10^5$。保证对于所有 $1 \leq i < m$，有 $x_i \leq x_{i+1}$（即能量提升点按非递减位置排序），并且没有能量提升点位于任何障碍物的区间内。

对于每个测试用例，输出她必须收集的最少能量提升点数才能到达位置 $L$。如果无法完成，则输出 $-1$。

In the first test case, she can collect power-ups $ 1 $ , $ 2 $ , $ 3 $ , and $ 5 $ to clear all hurdles. In the second test case, she cannot jump over the first hurdle. In the fourth test case, by collecting both power-ups, she can jump over the hurdle.