K. Plants Watering
time limit per test
1 second
memory limit per test
256 megabytes
input
plants.in
output
standard output

Pillow has a garden of plants of various heights, forming a beautiful line from left to right. Each plant grows with its own rate. Pillow had just taught The Captain about sorted sequences. The Captain wanted to know the first integer moment of time when the sequence of plants will become sorted in a non-decreasing order according to height.

Formally, you are given two arrays $$$h$$$ and $$$g$$$, where plant $$$i$$$ has a height of $$$h_i$$$ units initially, and each moment its height increases by $$$g_i$$$ units.

Find the first integer moment of time when the sequence of plants will become sorted in non-decreasing order according to height.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of plants.

The second line contains $$$n$$$ space-separated integers denoting the array $$$h$$$ $$$(1 \leq h_i \leq 10^9)$$$.

The third line contains $$$n$$$ space-separated integers denoting the array $$$g$$$ $$$(1 \leq g_i \leq 10^9)$$$.

Output

If there's no such moment, print "-1". Otherwise, print the first one.

Examples
Input
5
1 2 3 4 5
5 4 3 2 1
Output
0
Input
4
2 3 1 4
1 2 4 3
Output
1
Input
4
3 2 4 1
3 2 5 20
Output
-1