Minimum Number Satisfying Modular Conditions

Given two sets of numbers, each containing k integers. The first set is denoted by \(a_1,a_2,\dots,a_k\) and the second set by \(b_1,b_2,\dots,b_k\). It is guaranteed that the numbers in the second set are pairwise coprime. Find the smallest \(n\in \mathbb{N}\) such that for every \(i\in [1,k]\) the condition \(b_i\mid (n - a_i)\) holds.

inputFormat

The input consists of three lines. The first line contains an integer \(k\) representing the number of elements in each set. The second line contains \(k\) space-separated integers \(a_1,a_2,\dots,a_k\). The third line contains \(k\) space-separated integers \(b_1,b_2,\dots,b_k\).

outputFormat

Output the smallest integer \(n\) satisfying the conditions.

sample

2
1 2
3 5

7