题目描述

在日蚀节当晚，庙会举办了一场烟花表演。现场布置了 $n$ 枚烟花，第 $i$ 枚烟花将在第 $x_i$ 秒开始时于 $(x_i, 0)$ 处升空。烟花升空后，以每秒 $1$ 单位的速度沿 $y$ 轴正方向竖直上升，并在到达坐标 $(x_i, y_i)$ 时爆炸。数据保证，不存在两个烟花在同一时刻爆炸。

为了防止像素塔关闭，破碎数据研究所（BDRG）研发了一款反编译程序，并指派豌豆特工将其安装在部分烟花上。被安装了程序的烟花称为特殊烟花。

程序在烟花爆炸时运行，并通过附近的基站与其他用户建立联系。由于程序运行过程中各步骤之间需要进行数据传输，且传输距离受限，因此任意两个在爆炸时间上相邻的特殊烟花之间爆炸时的曼哈顿距离不得超过 $k$。两个特殊烟花在爆炸时间上相邻当且仅当不存在特殊烟花爆炸时间在它们的爆炸时间之间。两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

为了确保系统的鲁棒性，避免因部分烟花失效导致计划失败，高层希望特殊烟花的数量尽可能多。豌豆特工需要你帮忙计算：在满足上述条件的前提下，最多可以安装多少个特殊烟花？以及达到该最大数量的安装方案有多少种？答案对 $998244353$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示烟花的总数和允许的最大曼哈顿距离。

接下来 $n$ 行，每行包含两个整数 $x_i, y_i$，表示第 $i$ 个烟花的坐标。

输出格式

输出一个整数，表示特殊烟花最多的安装个数，以及达到该最大数量的安装方案数对 $998244353$ 取模的结果。

输入样例

4 2
1 1
2 2
3 2
2 4

输出样例

3 2

说明提示

样例解释

烟花按爆炸时间排序为：

• 第 $1$ 枚：$(1,1)$，$t=2$
• 第 $2$ 枚：$(2,2)$，$t=4$
• 第 $3$ 枚：$(3,2)$，$t=5$
• 第 $4$ 枚：$(2,4)$，$t=6$

要求选出的特殊烟花在爆炸时间上相邻时，它们的曼哈顿距离不超过 $k = 2$。

可能的选取方案：

• 选取烟花 $1$、$2$、$3$：检查距离 $|1-2|+|1-2|=2\le 2$，$|2-3|+|2-2|=1\le 2$，可行。
• 选取烟花 $1$、$2$、$4$：距离 $|1-2|+|1-2|=2\le 2$，$|2-2|+|2-4|=2\le 2$，可行。

无法选取全部 $4$ 枚（因为烟花 $3$ 与 $4$ 的距离为 $|3-2|+|2-4|=3>2$），也无法选出其他 $3$ 枚的组合（如 $2$、$3$、$4$ 中 $3$ 与 $4$ 距离超限，$1$、$3$、$4$ 中 $1$ 与 $3$ 距离超限）。因此最多可选 $3$ 枚，共有 $2$ 种方案，输出为 3 2。

数据范围

对于所有测试点，均满足：

• $1 \leq n \leq 10^6$
• $1 \leq k \leq 2 \times 10^9$
• $1 \leq x_i, y_i \leq 10^9$
• 保证不存在两个烟花在同一时刻爆炸

特殊性质 A：$k=1$

特殊性质 B：$k=2\times10^9$

特殊性质 C：$\forall i \in [1,n], x_i = y_i$

注：编号为 $i$ 的大样例满足子任务 $i$ 的限制

本站补充：原套别：第 11 套 D 题。

本站补充：附件勘误：原附 luminescence8.out 为 429966 1；依题意应为 1000000 1。该组所有爆炸时刻互异，任意两点距离均小于 k，因此全部点构成唯一最大集合。原附件保留供核对。