240214 - 区间完全覆盖

题目描述

给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间,即起点和和终点都包含在区间内),求最少使用多少条线段可以将整个区间完全覆盖。

输入

第一行包含 2 个整数,分别表示区间的长度 m 和线段的数量 n(1 <= n <= 100) ;

接下来 n 行,每行 2 个整数,分别表示线段的左端点和右端点。

输出

输出共一行,如果可以完全覆盖整个区间,则输出一个整数,表示至少需要多少线段可以完全覆盖整个区间,如果无法覆盖输出 "No"。

样例

输入

8 7
2 6
1 4
3 6
3 7
6 8
2 4
3 5

输出

3

输入

8 7
2 6
1 4
3 6
3 7
6 7
2 4
3 5

输出

No
说明

对于样例1,选择区间 [1,4] [3,7] [6,8] 即可完全覆盖,因此输出 3 ;

对于样例2,无论如何选择都无法覆盖到 8 的位置,因此输出 No 。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 35
通过人数 17
金币数量 3 枚
难度 基础


上一题 下一题