#1282. bella的超级能量波

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 丸山彩

题目描述

A-SOUL一行人决定去海滩游玩。不幸的是,海岸线上全都是小怪兽。海岸线的长度为 ,则小怪兽存在于 范围内(包括 )的每一个整数点上。

贝拉作为A-SOUL的队长,决定在她们前往海滩之前清理掉小怪兽。贝拉可以发动 种能量波,每种能量波只能发动一次,第 种能量波可以清理掉 范围内(包括 )的小怪兽。贝拉武艺高超,保证每一个小怪兽都有至少一种能量波可以清理掉。

贝拉是大聪明,于是她决定让你帮忙计算一下她最少需要发动多少次能量波就可以清理掉所有的小怪兽。这样贝拉就可以花费最短的时间完成任务,然后回家突击检查嘉然是不是在偷吃零食。

输入格式

第一行两个正整数 ,用空格隔开,表示海岸线的长度和能量波的种数。

接下来 行,每行两个正整数 ,用空格隔开,表示第 种能量波的攻击范围。

输出格式

一行一个整数,表示最少的能量波发动次数。

样例

输入样例1

3 3
1 2
2 3
2 2

输出样例1

2

输入样例2

4 2
1 4
1 4

输出样例2

1

输入样例3

4 2
1 2
3 4

输出样例3

2