题目描述

以下のような、無限に広い六角形のグリッドがあります。

六角形のマスは $2$ つの整数 $i,j$ を用いて $(i,j)$ と表されます。
マス $(i,j)$ は以下の $6$ つのマスと辺で隣接しています。

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

$2$ つのマス $X,Y$ の距離を、辺で隣接しているマスをたどってマス $X$ からマス $Y$ まで移動するときの、移動回数の最小値と定めます。
例えばマス $(0,0)$ とマス $(1,1)$ の距離は $1$、マス $(2,1)$ とマス $(-1,-1)$ の距離は $3$ です。

$N$ 個のマス $(X_1,Y_1),\ldots,(X_N,Y_N)$ が与えられます。
この $N$ マスの中から $1$ つ以上のマスを選ぶ方法のうち、選んだマスのうちどの $2$ マスの距離も $D$ 以下になるようなものは何通りありますか？
$998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $D$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$

输出格式

答えを出力せよ。

题目大意

给定正六边形网格：格子 $(x,y)$ 与 $(x-1,y),(x+1,y),(x,y-1),(x,y+1),(x+1,y+1),(x-1,y-1)$ 紧邻。

现在给定你网格中若干个格子 $(X_i,Y_i)$，请你求出，选择若干个格子，其中两两距离不超过给定值 $D$ 的方案数。两种方案不同当且仅当存在一个格子在一个方案中出现而在另一个方案中未出现。

答案对 $998244353$ 取模。

其中两个格子的距离：一个格子可以花费 $1$ 代价到达与其紧邻的一个格子，两个格子间距离的定义为在所有起点为其中一个格子，终点为另一个格子的路径中，花费总和的最小值。

数据范围：$1\leqslant N\leqslant 300,|X_i|,|Y_i|\leqslant 10^9,1\leqslant |D|\leqslant 10^{10}$

3 1
0 0
0 1
1 0

5

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

提示

制約

• $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)$ は相異なる
• 入力は全て整数である

Sample Explanation 1

選ぶマスの集合として考えられるのは $ \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},\{(0,0),(1,0)\} $ の $5$ 通りです。