距初始位置的距离 L 玩一个游戏,您骑自行车沿着笔直的路线到达遥远的目的地。
在这个游戏中,从初始位置到目的地的路线上,地面上自行车可以行驶的地方有限。 这里,自行车可以行驶的区域称为地面。 地面是 N 间隔 由 [a_i,b_i](i=1,…,N) 代表, 距初始位置的距离 有 x 对于 i 如果满足 a_i \leq x \leq b_i ,则表示此时自行车可以在地面上行驶。
自行车会自动匀速向前行驶,但如果自行车在地面上行驶,玩家可以让自行车跳跃。 当您跳跃时,您的自行车立即飞到空中,距离不远。 W 前进时着陆。 在空中飞行时,可以经过地面以外的区域,但着陆点必须在地面上。 另外,着陆点不能超过目标。 在一场游戏中你可以无限次跳跃,落地后可以立即再次跳跃。 完成一系列的跳跃后,自行车会自动再次向前行驶。
求自行车在不跑到地面以外任何地方的情况下到达目标所需的最小跳跃次数。
然而,如果无论你怎么跳都无法让自行车到达目标, -1 。
图 H. 输入示例 1 中如何骑自行车的示例
入力形式
输入按以下格式给出。
N L W a_1 b_1 … a_N b_N
出力形式
打印自行车到达终点线所需的最小跳跃次数。
但如果无法进球, -1 。
制約
- 1 \leq N \leq 10^5
- 1 \leq L \leq 10^9
- 1 \leq W \leq L
- a_i \lt b_i
- b_i \lt a_{i+1}
- a_1=0, b_N=L
- 所有输入值均为整数。
入出力例
入力例1
2 10 4 0 4 6 10
出力例1
1
入力例2
5 40 10 0 1 9 11 19 21 29 31 39 40
出力例2
4
入力例3
4 13 6 0 1 2 3 5 6 12 13
出力例3
2
入力例4
2 10 7 0 1 9 10
出力例4
-1