有 $n$ 位被编号的智者。每位智者都有一个写有整数的帽子。每位智者都能看到其他所有智者帽子上的数字，但看不到自己帽子上的数字。设 $a_i$ 表示第 $i$ 位智者帽子上的数字。

还有两个长度均为 $n-1$ 的整数数组：$b$ 和 $c$。如果存在至少一个 $i$（$1 \le i \le n - 1$）满足以下条件之一，则称这种给帽子分配数字的方案是合法的：

1. $a_{i+1} < a_i + b_i$
2. $a_{i+1} > a_i + c_i$

智者们知道实际的分配方案（即数组 $a$）是合法的。

接下来的过程如下：从第一天开始，每天开始时，如果存在一位编号为 $i$ 的智者，他知道某个整数 $x$ 满足 $a_i \ne x$（即他知道一个绝对没有写在自己帽子上的数字），他就会在当天结束时宣布这一点，随后该过程结束。如果没有这样的智者，该过程将在第二天继续，以此类推。

计算该过程是否会结束，如果会，计算它将在第几天结束。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示智者的数量。

第二行包含 $n$ 个整数 $a_i$（$-10^{10} \le a_i \le 10^{10}$）。

第三行包含 $n - 1$ 个整数 $b_i$（$-10^{10} \le b_i \le 10^{10}$）。

第四行包含 $n - 1$ 个整数 $c_i$（$-10^{10} \le c_i \le 10^{10}$）。

保证数组 $a$ 是合法的。

输出格式

如果该过程永远不会结束，输出 -1。否则，输出该过程结束的天数。

样例

输入样例 1

3
1 2 3
0 0
0 0

输出样例 1

2

输入样例 2

2
-1 -1
1
-1

输出样例 2

-1

输入样例 3

7
1 4 2 -5 10000000000 6 -7
-1 2 -3 4 6 5
2 3 322 5 100 312

输出样例 3

5

输入样例 4

8
3 2 8 25 16 24 24 24
-1 0 3 4 -2 7 6
-1 2 7 5 -1 12 11

输出样例 4

4

说明

考虑第一个样例。由数组 $b$ 和 $c$ 给出的限制可以重新表述为“并非所有整数都相等”。

在第一天，没有智者能够推断出一个没有写在自己帽子上的数字。

在第二天，第三位智者知道，如果他帽子上的数字是 2，那么在第一天，第一位智者就会看到其他两位智者帽子上的数字都是 2，从而推断出自己没有戴着写有 2 的帽子。因此，在第二天，第三位智者知道自己没有戴着写有 2 的帽子。

这好懂吗？可能不好懂。能用更好懂的方式来表述吗？可能也不行。