Equal :
Difficulty Level : Medium
Submissions : 141
Asked In :
Marks :20
: 3 | : 1
You are given 2 arrays $$$a_1,a_2...a_n$$$ and $$$b_1,b_2,...b_n$$$. In each steps you can set $$$a_i$$$ to $$$a_i-b_i$$$ if $$$a_i>=b_i$$$
Determine minimum number of steps to make all $$$a's$$$ equal.
Input
The first line contains $$$1\le n \le 5000$$$.
The second line contains $$$n$$$ space separated integers where $$$i_{th}$$$ integer represents $$$1\le a_i \le 5000$$$.
The third line contains $$$n$$$ space separated integers where $$$i_{th}$$$ integer represents $$$1\le b_i \le 5000$$$.
Output
Print minimum steps required to make all $$$a's$$$ equal . If it is not possible print $$$-1$$$.
Examples
Input
2 5 6 4 3
Output
-1
Input
5 5 7 10 5 15 2 2 1 3 5
Output
8
