H. Match of the Millennium
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The match of the century in the game of boulders has just ended. Its result has already been broadcast by all channels around the world. But soon the match of the millennium will begin, and preparations must be made.

As is known, this game uses $$$N$$$ piles of boulders, each of which must be in a specific predetermined ratio with all the others. Moreover, it does not matter how many boulders are in each pile; during preparation, it is only necessary to maintain the specified proportion. However, it is not allowed to leave all piles empty!

Unfortunately, the previous players did not clean up after themselves, and this task has been assigned to Vadim. He can remove one boulder from one pile in one minute, and he can also roll one boulder to any pile in one minute. This is an incredibly labor-intensive and time-consuming task, so it needs to be done as quickly as possible. Help Vadim determine the minimum time required to prepare for the match of the millennium.

Input

The first line contains an integer $$$N$$$ — the number of piles of boulders in the game $$$(2 \le N \le 10^5)$$$.

The second line contains $$$N$$$ integers $$$s_i$$$ — the number of boulders in each pile remaining after the match of the century $$$(1 \le s_i \le 10^9)$$$.

The third line contains $$$N$$$ integers $$$p_i$$$ — the required ratio of boulders in each pile to start the game $$$(1 \le p_i \le 10^9)$$$.

Output

Output a single integer — the minimum time required to prepare the piles for the match of the millennium.

Example
Input
2
21 34
2 3
Output
2
Note

In the example, Vadim needs to roll a boulder to the first pile and then remove one boulder from the second pile. Then the piles will have $$$22$$$ and $$$33$$$ boulders respectively, which satisfies the ratio of $$$2:3$$$.