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

[ABC280G] Do Use Hexagon Grid 2

Score : 600600 points

Problem Statement

We have an infinite hexagonal grid shown below.

A hexagonal cell is represented as (i,j)(i,j) with two integers ii and jj. Cell (i,j)(i,j) is adjacent to the following six cells:

  • (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)

Let us define the distance between two cells XX and YY by the minimum number of moves required to travel from cell XX to cell YY by repeatedly moving to an adjacent cell. For example, the distance between cells (0,0)(0,0) and (1,1)(1,1) is 11, and the distance between cells (2,1)(2,1) and (1,1)(-1,-1) is 33.

You are given NN cells (X1,Y1),,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N). How many ways are there to choose one or more from these NN cells so that the distance between any two of the chosen cells is at most DD? Find the count modulo 998244353998244353.

Constraints

  • 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) are pairwise distinct.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN DD

X1X_1 Y1Y_1

\vdots

XNX_N YNY_N

Output

Print the answer.

3 1
0 0
0 1
1 0
5

There are five possible sets of the chosen cells: {(0,0)},{(0,1)},{(1,0)},{(0,0),(0,1)}\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}, and {(0,0),(1,0)}\{(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