F - Manhattan Cafe Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 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

1 5
0
3

出力例 1

8

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

入力例 2

3 10
2 6 5
2 1 2

出力例 2

632

入力例 3

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

出力例 3

145428186

Score : 500 points

Problem Statement

In an N-dimensional space, the Manhattan distance d(x,y) between two points x=(x_1, x_2, \dots, x_N) and y = (y_1, y_2, \dots, y_N) is defined by:

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

A point x=(x_1, x_2, \dots, x_N) is said to be a lattice point if the components x_1, x_2, \dots, x_N are all integers.

You are given lattice points p=(p_1, p_2, \dots, p_N) and q = (q_1, q_2, \dots, q_N) in an N-dimensional space.
How many lattice points r satisfy d(p,r) \leq D and d(q,r) \leq D? Find the count modulo 998244353.

Constraints

  • 1 \leq N \leq 100
  • 0 \leq D \leq 1000
  • -1000 \leq p_i, q_i \leq 1000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D 
p_1 p_2 \dots p_N
q_1 q_2 \dots q_N

Output

Print the answer.

Sample Input 1

1 5
0
3

Sample Output 1

8

When N=1, we consider points in a one-dimensional space, that is, on a number line.
8 lattice points satisfy the conditions: -2,-1,0,1,2,3,4,5.

Sample Input 2

3 10
2 6 5
2 1 2

Sample Output 2

632

Sample Input 3

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

Sample Output 3

145428186