P2273【HN09 day1】邪恶的大叔 | |
|
问题描述
一个邪恶的大叔进入了这个神秘的空间,他发现这里有很多很多的Loli在这里,这个邪恶的大叔想把她们全部推倒!但是推倒Loli要耗费的体力太大了,所以他想用尽量少的次数把他们全部推倒。
所有的Loli可以抽象成一个一维的坐标系,第i个Loli所在的位置为Xi,她的身高为Hi。大叔可以推倒任意个Loli让她们向左或者向右倒下去,第i个Loli倒下去之后可能会连带着别的Loli一起倒下去(向左倒就是在她左边并且满足|Xi-Xj|≤Hi的所有Loli也会一起向左倒,向右同样计算)。
你的任务是帮助大叔计算出最少推倒多少个Loli可以让所有的Loli全部倒下。
输入格式
第一行一个整数N,表示Loli的个数。
以下N行每行两个整数Xi Hi,分别表示第i-1个Loli的位置和她的身高。
输入保证Xi递增输入。
输出格式
输出一行一个整数,表示大叔最少推倒的次数。
样例输入
6
1 1
2 2
3 1
5 1
6 1
8 3
样例输出
2
提示
【样例解释】
向右推倒第1个Loli可以让第2、3个Loli一起倒下。
向左推倒第6个Loli可以让第5、6个Loli一起倒下。
【数据约定】
对于30%的数据,满足N≤10
对于50%的数据,满足N≤1000
对于100%的数据,满足N≤100000;Hi≤108;Xi≤231。