Description

There are two groups of numbers, each with $k$ elements.

The numbers in the first group are denoted by $a_1,a_2,\cdots ,a_k$, and the numbers in the second group are denoted by $b_1,b_2,\cdots ,b_k$.

The numbers in the second group are pairwise coprime. Find the smallest $n\in \mathbb{N}$ such that for $\forall i\in [1,k]$, $b_i | (n-a_i)$ holds.

Input Format

The first line contains an integer $k$.

The second line contains $k$ integers: $a_1,a_2,\cdots ,a_k$.

The third line contains $k$ integers: $b_1,b_2,\cdots ,b_k$.

Output Format

Output a single integer, which is the required answer $n$.

3
1 2 3
2 3 5

23

Hint

Constraints:

$1\le k \le 10$，$|a_i|\le 10^9$，$1\le b_i\le 6\times 10^3$，$\prod_{i=1}^k b_i\le 10^{18}$.

Time limit per test case: 1 second.

Note: For C/C++ language, 64-bit integers should be declared as long long.

If using scanf and printf (as well as fscanf, fprintf, etc.), use the %lld specifier.

Translated by ChatGPT 5