配点 : $500$ 点

問題文

$N$ 次元空間上の $2$ 点 $x=(x_1, x_2, \dots, x_N)$, $y = (y_1, y_2, \dots, y_N)$ のマンハッタン距離 $d(x,y)$ は次の式で定義されます。

$$\displaystyle d(x,y)=\sum_{i=1}^n \vert x_i - y_i \vert $$

また、座標成分 $x_1, x_2, \dots, x_N$ がすべて整数であるような点 $x=(x_1, x_2, \dots, x_N)$ を格子点と呼びます。

$N$ 次元空間上の格子点 $p=(p_1, p_2, \dots, p_N)$, $q = (q_1, q_2, \dots, q_N)$ が与えられます。 $d(p,r) \leq D$ かつ $d(q,r) \leq D$ であるような格子点 $r$ としてあり得るものは全部で何個ありますか？答えを $998244353$ で割ったあまりを求めてください。

制約

• $1 \leq N \leq 100$
• $0 \leq D \leq 1000$
• $-1000 \leq p_i, q_i \leq 1000$
• 入力される値はすべて整数

入力

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

$N$ $D$

$p_1$ $p_2$ $\dots$ $p_N$

$q_1$ $q_2$ $\dots$ $q_N$

出力

答えを出力せよ。

1 5
0
3

8

$N=1$ の場合は $1$ 次元空間、すなわち数直線上の点に関する問題になります。 条件を満たす点は $-2,-1,0,1,2,3,4,5$ の $8$ 個です。

3 10
2 6 5
2 1 2

632

10 100
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

145428186