题目描述

John 正在森林里伐木，有 \(n\) 棵树排成一行（可以看成一条马路、直线），这 \(n\) 棵树的坐标分别为 \(x_1,x_2,…,x_n\)，每棵树的高度为 \(h_i\)。当 John 砍下一棵树时， 他可以把这棵树放在树的左边或右边，它占据了马路的一段 \([x_i-h_i, x_i]\) 或 \([x_i+h_i, x_i]\)，没有砍下的树占据了 \(x_i\) 点。当一棵树的左边 \([x_i-h_i, x_i]\) 段或右边 \([x_i+h_i, x_i]\) 段已经被其他倒下的树或未被砍下的树占据时，这棵树就不能被砍下。现在编程帮助 John 来计算，他最多可以砍下多少棵树。

注意：放置倒下的树时，允许使用负坐标，见样例解释。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 10^5)\)，接下来 \(n\) 行，每行两个正整数 \(x_i\) 和 \(t_i(1≤x_i,t_i≤10^6)\)。注意：所有树的坐标保证各不相同，数据中以 \(x_i\) 的升序给出。

输出格式

对于每组数据，输出一个正整数，表示 John 能砍树的最大数目。

样例1

输入样例1

2           
5
1 2
2 1
5 10
10 9
19 1
5
1 2
2 1
5 10
10 9
20 1

输出样例1

3
4

样例解释

样例 \(1.1\) 中，砍下第 \(1,2,5\) 棵树，分别占据 \([-1,1][2,3][5][10][19,20]\)；
样例 \(1.2\) 中，可以多砍下第 \(4\) 棵树，它可以占据 \([10,19]\) 且不影响砍第 \(5\) 棵树。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T2\)

文件IO

freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);