#1187. Parking Ships

Parking Ships

【问题描述】

有n(n<=1000)个海盗,每个海盗有一条船,长度为Li(1<=li<=10​^9^​)。他们的家沿着海边排成一条直线,每一个海盗家的坐标为xi(-10​^9^​<=xi<=10​^9^​)。他们会将船也停在海边(船相当于一个闭区间,两两不能相交)。如果某个海盗的船停在家门口(即他家的坐标包含在船所停的区间中),他会很高兴。

有个海盗是老大,他一定要自己的船放在家门口正当中(即他家坐标是他的船的区间中点)。请问怎样安排这些船只停靠才能让最多能让多少的海盗开心呢?

【输入格式】

第1行有一个整数,代表测试数据组数。对于每组测试数据而言包含2行,其中:

第1行有一个整数n,代表海盗的个数。

第2-n行,每行包含两个整数xi和li,含义如题目所述,第一对xi,li即海盗老大的家的坐标和船的长度。

【输出格式】

对每组测试数据,输出一个整数,代表最多能让多少海盗开心。你可以假设海岸是无限长的。

【输入输出样例】

样例输入

2
5
0 6
-5 2
-4 1
4 2
5 3
4
0 4
-5 4
3 4
5 3

样例输出

5
3