通常人们将新年与圣诞树和节日餐桌联系在一起，但学生们却将新年与考试季联系在一起。现在是 12 月 31 日，二年级学生已经报名参加考试。
共有 $n$ 天可以参加考试。每位学生都报名了其中某一天。因此，在第 $i$ 天，有 $a_i$ 名学生想要参加考试，但这一天最多能容纳的学生人数为 $b_i$。
老师需要让所有学生都有机会参加考试，因此一些学生可能需要被调整到其他日期。老师可以选择任意数量的学生，并将他们分配到任意一天参加考试。
如果一名学生原本想在第 $i$ 天参加考试，而老师最终将其调整到了第 $j$ 天，那么该学生的“不满度”等于 $|i - j|$。
请帮助老师分配学生，使得对于所有的 $i$，在第 $i$ 天参加考试的学生人数不超过 $b_i$，并使所有学生中的最大不满度最小化。
输入格式
第一行包含一个整数 $n$ —— 学生可以参加考试的天数 ($1 \le n \le 10^6$)。
第二行包含 $n$ 个整数 $a_i$ —— 第 $i$ 天想要参加考试的学生人数 ($1 \le a_i \le 10^9$)。
第三行包含 $n$ 个整数 $b_i$ —— 第 $i$ 天最多能容纳的学生人数 ($0 \le b_i \le 10^9$)。
输出格式
输出一个整数，表示使得任何学生的不满度都不超过 $k$ 的最小 $k$ 值。如果无解，请输出 $-1$。
样例
输入 1
4 6 14 70 1 70 3 16 5
输出 1
2
输入 2
1 2 2
输出 2
0
输入 3
1 3 2
输出 3
-1
说明
考虑第一个样例。注意，有 70 名学生想在第三天参加考试，但第 2、3、4 天总共只能容纳 24 名学生。因此答案至少为 2。
在第一个样例中，将学生移动使得没有任何学生被移动超过 2 天的一种方式如下：
- $6, 14, 70, 1$ — 学生的初始安排；
- $6, 70, 14, 1$ — 将第三天的所有学生移动到第二天，并将第二天的所有学生移动到第三天；
- $70, 6, 14, 1$ — 将第二天的所有学生移动到第一天，并将第一天的所有学生移动到第二天；
- $70, 6, 11, 4$ — 将三名学生从第三天移动到第四天；
- $70, 3, 14, 4$ — 将三名学生从第二天移动到第三天；
注意，每位学生从其初始计划位置移动的距离都没有超过两天。