← 返回题目列表

AtCoder · typical90_cc

081. 友好小组 (★5)

中文机器翻译题面 查看原题

配点: 5 点

問題文

典型高中的编号为 N 名学生,每个学生有 它的顺序为 1 减去 N 到。学生 i 的高度是 A_i、体重从 B_i 。

N 名学生中,选择不少于 1 人,组成满足以下所有条件的队伍。

  • 队伍中的任何 2 人,身高差的绝对值为 K 小于或等于
  • 队伍中的任何 2 人也请求出体重差绝对值 K 小于或等于

作为队伍人数可能的最大值。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 5000
  • 1 \leq A_i, B_i \leq 5000 \ (1 \leq i \leq N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

请打印答案。 到达


入力例 1

3 4
1 1
2 5
7 4

出力例 1

2

|A_1 - A_2| = |1 - 2| = 1 \leq K, |B_1 - B_2| = |1 - 5| = 4 \leq K 根据此,学生 1 和学生 2 选择 2 人可以组成一个队伍。

2 由于不能组成比人数更多的队伍 2 。


入力例 2

2 123
4 5
678 901

出力例 2

1

1 也可能只能组成 人队伍。


入力例 3

7 10
20 20
20 20
20 30
20 40
30 20
30 30
40 20

出力例 3

5

5 学生 它由 1, 2, 3, 5, 6 可以选择 来组成队伍。