#SYUCT13C. 月光小径

月光小径

题目描述

永夜异变之后,月亮被换成了假的,迷途竹林的夜晚格外昏暗。为了前往永远亭查明真相,博丽灵梦需要沿着一条由 LL 个首尾相接的单位路段组成的小径前进。

这些单位路段依次编号为

1,2,…,L.1,2,\ldots,L.

小径旁恰好有 nn 盏竹灯。点亮第 ii 盏竹灯后,它会照亮编号在闭区间

[li,ri][l_i,r_i]

内的所有单位路段,包括编号为 lil_i 和 rir_i 的路段。

灵梦想知道:最少点亮几盏竹灯,才能让编号为 1,2,…,L1,2,\ldots,L 的每个单位路段都被至少一盏灯照亮?

如果无论如何都无法照亮整条小径,请输出 −1-1。

输入格式

第一行输入两个整数 nn 和 LL(1≤n≤1051\le n\le 10^5,1≤L≤1091\le L\le 10^9),分别表示竹灯数量和单位路段数量。

接下来 nn 行,每行输入两个整数 lil_i 和 rir_i(1≤li≤ri≤L1\le l_i\le r_i\le L),表示第 ii 盏竹灯能够照亮编号从 lil_i 到 rir_i 的所有单位路段。

输出格式

输出一行一个整数:

  • 如果能够照亮整条小径,输出最少需要点亮的竹灯数量;
  • 否则输出 −1-1。

样例

3 10
1 6
2 3
5 10
2

提示

样例中,点亮第 11 盏竹灯(照亮编号 11 至 66 的路段)和第 33 盏竹灯(照亮编号 55 至 1010 的路段),即可照亮全部 1010 个单位路段,因此最少需要点亮 22 盏。

例如,一盏灯照亮编号 11 至 55 的路段,另一盏灯照亮编号 66 至 1010 的路段时,两者合计恰好照亮编号 11 至 1010 的所有单位路段,中间没有遗漏。

下载正式赛最终版 PDF 题面