区间计数

时间限制：2s
空间限制：1024MB

题目描述

给定满足 $x_1<x_2<\cdots<x_N$ 的正整数 $x_1,x_2,\ldots,x_N$，以及正整数 $y_1,y_2,\ldots,y_N$。

考虑满足下列条件的元组 $(M,L_1,R_1,\ldots,L_M,R_M)$：

• $M$ 是正整数；
• 对每个 $1\le j\le M$，$L_j,R_j$ 是满足 $L_j\le R_j$ 的整数；
• 对每个 $1\le i\le N$，恰有 $y_i$ 个下标 $j$ 满足 $L_j\le x_i\le R_j$。

可以证明这样的元组一定存在。求所有合法元组中 $\min\{R_j-L_j\mid1\le j\le M\}$ 的最大可能值；若该最大值不存在，输出 $-1$。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $x_1,x_2,\ldots,x_N$。

第三行 $N$ 个整数 $y_1,y_2,\ldots,y_N$。

输出格式

输出所求最大值；若最大值不存在，输出 $-1$。

样例输入 1

3
1 3 5
1 3 1

样例输出 1

2

样例输入 2

3
1 10 100
2 3 2

样例输出 2

-1

样例输入 3

7
10 31 47 55 68 73 90
3 7 4 6 3 4 4

样例输出 3

56

数据范围

• $1\le N\le2\times10^5$；
• $1\le x_1<x_2<\cdots<x_N\le10^9$；
• $1\le y_i\le10^9$。

在子任务 1 中约定 $y_0=y_{N+1}=0$。