← 返回题目列表

AtCoder · abc265_f

I. 曼哈顿咖啡馆

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

在 N维空间,曼哈顿距离 d(x,y) 两点之间 x=(x_1, x_2, \dots, x_N) 和 y = (y_1, y_2, \dots, y_N) 定义为:

\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 均为整数。

给你格子点 p=(p_1, p_2, \dots, p_N) 和 q = (q_1, q_2, \dots, q_N) 在 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,我们考虑一维空间中的点,即数轴上的点。
8 格点满足条件: AtCoder Railway 运营的某条线路上的 -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