Request Redirection

Assign requests to servers that can serve them. The final load of each server must be strictly less than max_req. Minimize the maximum cross-server distance.

This site's standard input/output format and supplementary bounds are as described in this problem.

输入格式

The first line contains n (1≤n≤10^5), the second line requests[n], and the third line max_req[n]; all values are non-negative/positive integers ≤10^9. Server positions follow the array indices.

输出格式

Output the minimum possible maximum redirection distance; output -1 if the total capacity is insufficient.

样例 1

输入：

2
5 0
4 10

输出：

1

样例 2

输入：

3
2 2 0
2 2 5

输出：

1

样例 3

输入：

2
4 4
3 3

输出：

-1