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 <= n <= 10^5)$ — the number of plants.
The second line contains $n$ space-separated integers denoting the array $h$ $(1 <= h_i <= 10^9)$.
The third line contains $n$ space-separated integers denoting the array $g$ $(1 <= g_i <= 10^9)$.
If there's no such moment, print "-1". Otherwise, print the first one.
## Input
The first line contains a single integer $n$ $(1 <= n <= 10^5)$ — the number of plants.The second line contains $n$ space-separated integers denoting the array $h$ $(1 <= h_i <= 10^9)$.The third line contains $n$ space-separated integers denoting the array $g$ $(1 <= g_i <= 10^9)$.
## Output
If there's no such moment, print "-1". Otherwise, print the first one.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the sizes of decks $ A $ and $ B $, respectively.
Let $ A = (a_1, a_2, \dots, a_n) $, $ B = (b_1, b_2, \dots, b_m) $ be sequences of integers with $ 1 \leq a_i, b_j \leq 20 $.
For any contiguous subarray $ A[l_A:r_A] = (a_{l_A}, a_{l_A+1}, \dots, a_{r_A}) $ and $ B[l_B:r_B] = (b_{l_B}, b_{l_B+1}, \dots, b_{r_B}) $, define:
- $ f(X) $: the multiset of unpaired cards remaining after repeatedly removing pairs of equal values from multiset $ X $.
- $ d_A(l_A, r_A, l_B, r_B) = |f(A[l_A:r_A])| $, the number of remaining cards in Alice’s hand.
- $ d_B(l_A, r_A, l_B, r_B) = |f(B[l_B:r_B])| $, the number of remaining cards in Bob’s hand.
**Constraints**
1. $ 1 \leq n, m \leq 10^5 $
2. $ 1 \leq a_i, b_j \leq 20 $
**Objective**
Compute:
$$
S_A = \sum_{l_A=1}^{n} \sum_{r_A=l_A}^{n} \sum_{l_B=1}^{m} \sum_{r_B=l_B}^{m} d_A(l_A, r_A, l_B, r_B) \mod 2^{32}
$$
$$
S_B = \sum_{l_A=1}^{n} \sum_{r_A=l_A}^{n} \sum_{l_B=1}^{m} \sum_{r_B=l_B}^{m} d_B(l_A, r_A, l_B, r_B) \mod 2^{32}
$$