After making your tasty breakfast, you are content and decided to head out to school. Even though your grandpa always tells you, "Well back in my day... I had to climb over mountains and traverse through the forests to get to school", but you thought, our journey is no different, right?

To get to school, there are $N$ streets you need to cross. Each street take negligible time to cross. At the $i$-th crossing, the pedestrain light only goes green every $a_i$ seconds. Initially, they are all green at the same time. You can only cross the street when the light is green. It takes time $b_i$ seconds to walk from crossing $i-1$ to $i$, and $b_0$ means the seconds it takes to walk from your home to the first crossing. When you cross the final street, you arrive at your school. What is the minimum time in seconds needed for you to go to school?

Input

The first line contains an integer $N$.
The second line contains $N$ integers, the period of the pedestrain light, $a_i$.
The third line contains $N$ integers, the walking time needed between streets $b_i$.

Output

Output the minimum time in seconds needed for you to go to school.

Constraints

For all test cases: $1 \le N \le 10^6, 1 \le a_i, b_i \le 10^9$.
Subtask 1 (50%): $N \le 10, a_i, b_i \le 1000$
Subtask 2 (50%): No other constraints