#8866. 「YACS2020年3月月赛」气球 普及−

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

题目描述

在一个二维坐标系上,悬浮着 只静止不动的气球,第 个气球的坐标为 表示它的横坐标,表示它的高度。保证在同一个坐上,最多只有一只气球。

小爱打算用最少的弓箭射穿所有的气球,每只弓箭射出时,需要确定一个高度,当弓箭没有遇到气球时,它会一直保持同样的高度沿 轴正方向运动,如果弓箭碰到

了气球,气球就会被射穿,弓箭的高度会减少 ,然后继续沿水平方向运动,直到遇到下一个气球。

请问,小爱最少需要射出多少只箭,才能将所有的气球全部射穿?

输入格式

第一行:单个正整数表示

接下来 行,每行两个整数,表示一只气球的坐标。

输出格式

单个正整数,表示最少需要多少只箭才能拿射穿所有的气球。

样例

样例输入 1

5
1 2 
3 5 
4 4 
5 3
2 1 

样例输出 1

2

样例解释 1

第一支箭的射穿高度为 2,1 的气球,第二支箭的射穿高度为 5,4,3 的气球

样例输入 2

5
1 1
2 2
5 5
3 3
4 4

样例输出 2

5

样例解释 2

每一只箭只能射穿一只气球

样例输入 3

5
4 1
1 4
2 5
3 2
5 4

样例输出 3

3

数据范围与提示

对于 的数据:

对于 的数据:

对于 的数据: