题目描述

数轴上有一个八爪鱼形状的机器人和 $N$ 个宝物。第 $i$ 个宝物（$1 \le i \le N$）的坐标是 $X_i$。

机器人有一个头和 $N$ 条腿，第 $i$ 条腿（$1\leq i\leq N$） 的长度是 $L_i$。

求使得机器人能抓获全部 $N$ 个宝物的整数 $k$ 的个数。机器人抓宝物的过程如下。

• 把机器人的头放置在坐标 $k$ 处。
• 对于 $i=1,2,\ldots,N$，依次进行下述动作：若有尚未抓获的宝物到机器人的头的距离不超过 $L_i$，即宝物的坐标 $x$ 满足 $k-L_i\leq x\leq k+L_i$，任选一个这样的宝物，把它抓获。

数据范围

• $1 \leq N\leq 200$
• $-10^{18} \leq X_1 < X_2 < \cdots < X_N\leq 10^{18}$
• $1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}$
• 输入的值都是整数。

输入

$N$

$X_1$ $X_2$ $\ldots$ $X_N$

$L_1$ $L_2$ $\ldots$ $L_N$

输出

输出满足题目所述条件的整数 $k$ 的个数。

样例

3
-6 0 7
3 5 10

6

$k=-3,-2,-1,2,3,4$ 满足条件。

1
0
1000000000000000000

2000000000000000001

从 $-10^{18}$ 到 $10^{18}$ 的所有整数 $k$ 都满足条件。

2
-100 100
1 1

0