atcoder#ABC280G. [ABC280G] Do Use Hexagon Grid 2

[ABC280G] Do Use Hexagon Grid 2

配点 : 600600

問題文

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

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

  • (i1,j1)(i-1,j-1)
  • (i1,j)(i-1,j)
  • (i,j1)(i,j-1)
  • (i,j+1)(i,j+1)
  • (i+1,j)(i+1,j)
  • (i+1,j+1)(i+1,j+1)

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

NN 個のマス (X1,Y1),,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N) が与えられます。 この NN マスの中から 11 つ以上のマスを選ぶ方法のうち、選んだマスのうちどの 22 マスの距離も DD 以下になるようなものは何通りありますか? 998244353998244353 で割ったあまりを求めてください。

制約

  • 1N3001 \leq N \leq 300
  • 109Xi,Yi109-10^9\leq X_i,Y_i \leq 10^9
  • 1D10101\leq D \leq 10^{10}
  • (Xi,Yi)(X_i,Y_i) は相異なる
  • 入力は全て整数である

入力

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

NN DD

X1X_1 Y1Y_1

\vdots

XNX_N YNY_N

出力

答えを出力せよ。

3 1
0 0
0 1
1 0
5

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

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