407722: GYM102881 K Plants Watering

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.

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)$$$.

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

5
1 2 3 4 5
5 4 3 2 1

0

4
2 3 1 4
1 2 4 3

1

4
3 2 4 1
3 2 5 20

-1