Hello codeforces, I want to know whether there is any solution to this problem that is better than the naive O(N ^ 2) or not?

Problem:

You are given two arrays A and B. In each step, you can set A[i] = A[i] — B[i] if A[i] >= B[i]. Determine the minimum number of steps that are required to make all values of array A equal.

Print the minimum number of steps that are required to make all values of array A equal. If it is not possible, then print -1.

Constraints:

1 <= N, A[i], B[i] <= 5000

Sample Input

2

5 6

4 3

Sample Output

-1

Sample Input:

5

5 7 10 5 15

2 2 1 3 5

Sample Output:

8

Link to the Problem