2663: 部队

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:6 解决:0

题目描述

王国军总指挥——卡西乌斯准将决定重建情报局,需要从全国各地挑选有能力的士兵,选择的标准为A,B两种能力。对于每个候选士兵,如果存在另一名士兵的两项能力均大于等于他,那么他将被淘汰。(注意:若两名士兵两项能力均相等,则认为排在后面被淘汰)。

 

可以认为,能力差别不大的士兵更适合在一个队伍中。(我们这样定义能力差别:设士兵iA,B能力值为aibi,士兵jA,B能力值为ajbj,那么他们的能差别为|ai-aj|+|bi-bj|

对于每个未被淘汰的士兵,只要某队伍中有另一个和他能力差别不大于k的士兵,他就可以加入该队伍。

现在,卡西乌斯想在符合以上条件的前提下,挑选出人数最多的队伍担当重任。

 

输入

1: 2个用空格隔开的整数:nk ,其中n表示候选士兵总数,k如题意所述。

2..n+1: i+1行用2个以空格隔开整数aibi,分别表示第i个士兵A,B两种能力的能力值。

输出

只有1个整数,表示最多人数。

样例输入 复制

5 3
2 11
4 10
3 9
1 12
6 8

样例输出 复制

3

提示

数据范围:20% 的数据1<=n<=1000

40% 的数据未被淘汰的士兵总数不会多于3000人。

100%的数据.1<=n<=100000,其余数据在[0,100000000]