2663: 部队
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:6
解决:0
题目描述
王国军总指挥——卡西乌斯准将决定重建情报局,需要从全国各地挑选有能力的士兵,选择的标准为A,B两种能力。对于每个候选士兵,如果存在另一名士兵的两项能力均大于等于他,那么他将被淘汰。(注意:若两名士兵两项能力均相等,则认为排在后面被淘汰)。
可以认为,能力差别不大的士兵更适合在一个队伍中。(我们这样定义能力差别:设士兵i的A,B能力值为ai,bi,士兵j的A,B能力值为aj,bj,那么他们的能差别为|ai-aj|+|bi-bj|)
对于每个未被淘汰的士兵,只要某队伍中有另一个和他能力差别不大于k的士兵,他就可以加入该队伍。
现在,卡西乌斯想在符合以上条件的前提下,挑选出人数最多的队伍担当重任。
输入
第1行: 2个用空格隔开的整数:n和k ,其中n表示候选士兵总数,k如题意所述。
第2..n+1行: 第i+1行用2个以空格隔开整数ai和bi,分别表示第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]。