曼哈顿咖啡馆

题目描述

在 $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) \le D$ 且 $d(q,r) \le D$？求答案对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

1 5
0
3

8

当 $N=1$ 时，我们考虑一维空间中的点，即在数轴上的点。

满足条件的格点有 $8$ 个：$-2,-1,0,1,2,3,4,5$。

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

数据范围

• $1 \le N \le 100$
• $0 \le D \le 1000$
• $-1000 \le p_i, q_i \le 1000$
• 输入中的所有值均为整数