407722: GYM102881 K Plants Watering

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Plants Wateringtime limit per test1 secondmemory limit per test256 megabytesinputplants.inoutputstandard 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.

ExamplesInput
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

Source/Category

加入题单

上一题 下一题 算法标签: