章鱼

题目描述

数轴上有 $1$ 只章鱼形机器人和 $N$ 个宝藏。

第 $i$ 个宝藏($1 \le i \le N$)位于坐标 $X_i$ 处。

机器人有 $1$ 个头和 $N$ 条腿,第 $i$ 条腿($1 \le i \le N$)的长度为 $L_i$。

求满足以下条件的整数 $k$ 的个数:将头放在坐标 $k$ 处,机器人可以抓住全部 $N$ 个宝藏。

将头放在坐标 $k$ 处。

按 $i=1,2,\dots,N$ 的顺序重复以下操作:如果头的距离 $L_i$ 范围内存在尚未被抓取的宝藏,即存在满足 $k-L_i \le x \le k+L_i$ 的坐标 $x$ 处的宝藏,则选择其中一个并抓取。

输入格式

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

$N$
$X_1$ $X_2$ $\dots$ $X_N$
$L_1$ $L_2$ $\dots$ $L_N$

输出格式

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

样例

3
-6 0 7
3 5 10

6

$k=-3,-2,-1,2,3,4$ 满足条件。例如,当 $k=-3$ 时,机器人可以按如下方式抓住全部三个宝藏。

第一条腿可以抓住满足 $-6 \le x \le 0$ 的坐标 $x$ 处的宝藏。其中,抓住坐标 $-6$ 处的第一个宝藏。

第二条腿可以抓住满足 $-8 \le x \le 2$ 的坐标 $x$ 处的宝藏。其中,抓住坐标 $0$ 处的第二个宝藏。

第三条腿可以抓住满足 $-13 \le x \le 7$ 的坐标 $x$ 处的宝藏。其中,抓住坐标 $7$ 处的第三个宝藏。

1
0
1000000000000000000

2000000000000000001

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

2
-100 100
1 1

0

不存在满足条件的 $k$。

数据范围

• $1 \le N \le 200$
• $-10^{18} \le X_1 \lt X_2 \lt \dots \lt X_N \le 10^{18}$
• $1 \le L_1 \le L_2 \le \dots \le L_N \le 10^{18}$
• 所有输入值均为整数。