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$$$ 来清除所有障碍。
在第二个测试用例中,她无法跳过第一个障碍。
在第四个测试用例中,通过收集两个道具,她可以跳过障碍。