选择围栏
测试数据来自 system/1575
背景
2009NOIP余姚中学内部暑期集训
7月14号模拟赛第二题
描述
给定n个单位宽度木板,你的任务是用这些木板在一条直线上组成一个围栏,且木板之间不能互相覆盖。
这些木板非常特殊,第i个木板必须被第i个钉子固定,而第i个钉子相对于原点的位置是给定的。你在钉子的左右移动,直到木板的边缘,因为钉子是没有宽度的,可以钉在木板的任何位置。
格式
输入格式
给定n,表示有n个木板n<=10000。
接下来n行,每行2个整数 Li and Pi (1 <= Li, Pi <= 100000),表示第i个木板的长度,以及它必须被固定在第i个钉子的位置。
输出格式
输出最多能选几个木板,组成围栏
样例1
样例输入1
7
5 9
2 17
6 10
3 11
2 16
4 13
5 6
样例输出1
5
限制
各个测试点1s
提示
5
30%的数据 n<=100;
100%的数据n<=10000;
木板的左端点可以为负