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 java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[200000];
		int b[] = new int[200000];
		int tmp[] = new int[200000];
		long ans = 0;

		for(int i = 0 ; i < n ; i++){
			a[i] = sc.nextInt();
		}
		for(int i = 0 ; i < n ; i++){
			b[i] = sc.nextInt();
			tmp[i] = b[i];
		}

		Boolean changed = true;
		int cnt = 0;

		while(changed){
			changed = false;
			if(b[0] > b[1] + b[n-1]){
					cnt = (tmp[0]-a[0]) / (b[1]+b[n-1]);
					tmp[0] -= (b[1]+b[n-1])*cnt;
					ans += cnt;
					if(cnt >= 1){
						changed = true;
					}
			}
			for(int i = 1 ; i < n-1 ; i++){
				if(b[i] > b[i+1] + b[i-1]){
						
						cnt = (tmp[i]-a[i]) / (b[i+1]+b[i-1]);
						tmp[i] -= (b[i+1]+b[i-1])*cnt;
						ans += cnt;
						if(cnt >= 1){
							changed = true;
						}
				}
			}
			if(b[n-1] > b[0] + b[n-2]){
					cnt = (tmp[n-1]-a[n-1]) / (b[0]+b[n-2]);
					tmp[n-1] -= (b[0]+b[n-2])*cnt;
					ans += cnt;
					if(cnt >= 1){
						changed = true;
					}
			}

			for(int i = 0 ; i < n ; i++){
				b[i] = tmp[i];
			}
		}

		for(int i = 0 ; i < n ; i++){
			if(a[i] != b[i]){
				ans = -1;
			}
		}

		System.out.println(ans);
	}

}