题目描述

在一个 $N$ 维空间中，两个点 $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=(x_1, x_2, \dots, x_N)$ 的分量 $x_1, x_2, \dots, x_N$ 都是整数，则称其为格点。

给定 $N$ 维空间中的两个格点 $p=(p_1, p_2, \dots, p_N)$ 和 $q = (q_1, q_2, \dots, q_N)$。
有多少个格点 $r$ 满足 $d(p,r) \\leq D$ 并且 $d(q,r) \\leq D$？将答案对 $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$ 时，我们考虑一维空间中的点，即在数轴上。
满足条件的格点有 $-2,-1,0,1,2,3,4,5$。

示例输入 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