← 返回题目列表

Codeforces · 2037/D

D. 鲨鱼冲浪

中文机器翻译题面 查看原题

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 \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$$$ 个加电的位置和值。可能有多个具有相同 $$$x$$$ 的强化道具。保证 $$$x_i \leq x_{i+1}$$$ 对于所有 $$$1 \leq i < m$$$ (即,加电按非递减位置排序),并且在任何障碍的间隔中都没有加电。

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

输出

对于每个测试用例,输出她必须收集才能到达位置 $$$L$$$ 的最小能量提升数量。如果不可能,则输出$$$-1$$$。

示例

输入 #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

输出 #1

4
-1
1
2

注意

在第一个测试用例中,她可以收集能量提升 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$5$$$ 来清除所有障碍。

在第二个测试用例中,她无法跳过第一个障碍。

在第四个测试用例中,通过收集两个道具,她可以跳过障碍。