当前没有测试数据。

G - 使用六角形网格2

得分：600分

题目描述

我们有一个无限的六角形网格如下所示。

一个六边形的单元格可以表示为$(i,j)$，其中$i$和$j$是两个整数。
单元格$(i,j)$与以下六个单元格相邻：

• $(i-1,j-1)$
• $(i-1,j)$
• $(i,j-1)$
• $(i,j+1)$
• $(i+1,j)$
• $(i+1,j+1)$

让我们用从单元格$X$到单元格$Y$的最小移动次数来定义两个单元格间的距离。
例如，单元格$(0,0)$和$(1,1)$的距离为$1$，单元格$(2,1)$和$(-1,-1)$的距离为$3$。

给定$N$个单元格$(X_1,Y_1),\ldots,(X_N,Y_N)$。
从这$N$个单元格中选择一个或多个，使得选择的任意两个单元格之间的距离最多为$D$的方式有多少种？
结果对$998244353$取模。

约束条件

• $1 \leq N \leq 300$
• $-10^9\leq X_i,Y_i \leq 10^9$
• $1\leq D \leq 10^{10}$
• $(X_i,Y_i)$ 两两不同。
• 输入中的所有值都是整数。

输入

输入从标准输入中按以下格式给出：

$N$ $D$

$X_1$ $Y_1$

$\vdots$

$X_N$ $Y_N$

输出

输出答案。

3 1
0 0
0 1
1 0

5

存在五种可能的选中单元格的集合：$\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}$和$\{(0,0),(1,0)\}$。

9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

33

5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482

31