题目描述

在平面直角坐标系中，有 $n$ 颗豆子，其中第 $i$ 颗豆子的的坐标为 $(x_i,y_i)$。

定义黑洞为：与 $x$ 轴平行的一条长度为 $k$ 的线段。特别地，若 $k=0$，则黑洞为一个点。

游戏开始后，所有豆子都会沿 $y$ 轴负方向（即向下）不停地运动。

你有两个黑洞，你可以将它们放置在任何地方（黑洞坐标可以为负数），用黑洞来接住这些豆子。若在某一时刻，一颗豆子遇到了黑洞，则这颗豆子被接住，并且停止运动。若一个豆子永远无法遇到黑洞，则它将会丢失。

请你设计一种方案，使接到的豆子的个数最大，并输出最大的个数。

输入格式

从文件 bean.in 中读入数据。

本题多测。第一行两个正整数 $c,T$，表示该测试点的编号和测试数据的组数。

接下来 $T$ 组数据，每组数据的格式如下：

• 第一行两个正整数 $n,k$，表示豆子的个数和黑洞的长度。
• 接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示豆子的坐标。

输出格式

输出到文件 bean.out 中。

对于每组数据，输出一行一个正整数，表示最多接住多少个豆子。

输入输出样例

1 1
8 2
1 1
1 2
2 5
4 4
5 3
6 2
6 4
7 3

7

【样例 #1 解释】

两个黑洞的左端点可能为 $(0,0)$ 和 $(4,1)$，如图：

可以接住图中的红点，数量为 $7$。可以证明这是最优方案之一。

【样例 #2】

见附件的 bean/bean2.in 与 bean/bean2.ans。

该样例满足 1 号测试点的性质。

【样例 #3】

见附件的 bean/bean3.in 与 bean/bean3.ans。

该样例满足 2 号测试点的性质。

【样例 #4】

见附件的 bean/bean4.in 与 bean/bean4.ans。

该样例满足 4 号测试点的性质。

【样例 #5】

见附件的 bean/bean5.in 与 bean/bean5.ans。

该样例满足 6 号测试点的性质。

【样例 #6】

见附件的 bean/bean6.in 与 bean/bean6.ans。

该样例满足 8 号测试点的性质。

数据范围

对于所有数据，保证：

• $1 \le T \le 5$
• $1 \le n \le 10^5$
• $0 \le k \le 10^9$
• $1 \le x_i,y_i \le 10^9$

测试点编号	$n \le$	$k \le$	$x_i,y_i \le$	特殊性质
$1$	$10$			否
$2 \sim 3$	$10^5$	$0$	$10^9$
$4 \sim 5$		$10^9$		是
$6 \sim 7$	$10^3$			否
$8 \sim 10$	$10^5$	$10^9$

特殊性质：不同的横坐标的数量不超过 $3$。

附件下载

链接