There are N positive integers arranged in a circle.

Now, the i-th number is A_i. Takahashi wants the i-th number to be B_i. For this objective, he will repeatedly perform the following operation:

* Choose an integer i such that 1 \leq i \leq N.
* Let a, b, c be the (i-1)-th, i-th, and (i+1)-th numbers, respectively. Replace the i-th number with a+b+c.



Here the 0-th number is the N-th number, and the (N+1)-th number is the 1-st number.

Determine if Takahashi can achieve his objective. If the answer is yes, find the minimum number of operations required.

Constraints

* 3 \leq N \leq 2 \times 10^5
* 1 \leq A_i, B_i \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N
B_1 B_2 ... B_N


Output

Print the minimum number of operations required, or `-1` if the objective cannot be achieved.

Examples

Input

3
1 1 1
13 5 7


Output

4


Input

4
1 2 3 4
2 3 4 5


Output

-1


Input

5
5 6 5 2 1
9817 1108 6890 4343 8704


Output

25
import math
import heapq

N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

num = 0
i = 0
comp = 0
for i in range(N):
	if A[i] == B[i]:
		comp += 1
	elif A[i] > B[i]:
		print(-1)
		exit()
i = 0

while comp < N:
	loc = i % N
	loc_plus = (i + 1) % N
	loc_minus = (i - 1) % N
	if B[loc] >= B[loc_plus] and B[loc] >= B[loc_minus] and A[loc] < B[loc]:
		big = max(B[loc_minus], B[loc_plus])
		if big <= A[loc]:
			if (B[loc] - A[loc]) % (B[loc_minus] + B[loc_plus]) == 0:
				comp += 1
				num += (B[loc] - A[loc]) // (B[loc_minus] + B[loc_plus])
				B[loc] = A[loc]
			else:
				print(-1)
				exit()
		else:
			n = math.ceil((B[loc] - big + 1)/(B[loc_minus] + B[loc_plus]))
			num += n
			B[loc] -= n*(B[loc_minus] + B[loc_plus])
			if B[loc] < A[loc]:
				print(-1)
				exit()
			elif B[loc] == A[loc]:
				comp += 1
		if B[loc_plus] > B[loc_minus]:
			i = loc_plus
		else:
			i = loc_minus
	elif (B[loc] < B[loc_plus] or B[loc] < B[loc_minus]) and A[loc] < B[loc]:
		if B[loc_plus] >= B[loc_minus]:
			loc_next = loc_plus
		else:
			loc_next = loc_minus
		if B[loc_next] == A[loc_next]:
			print(-1)
			exit()
		else:
			i = loc_next
	elif A[loc] == B[loc]:
		i += 1
	#print(B, num, loc)
print(num)