题目描述

现有两组数字，每组$k$个。

第一组中的数字分别用$a_1,a_2,\cdots ,a_k$表示，第二组中的数字分别用$b_1,b_2,\cdots ,b_k$表示。

其中第二组中的数字是两两互素的。求最小的$n\in \mathbb{N}$，满足对于$\forall i\in [1,k]$，有$b_i | (n-a_i)$。

输入输出格式

输入格式

第一行一个整数$k$。

第二行$k$个整数，表示：$a_1,a_2,\cdots ,a_k$。

第三行$k$个整数，表示：$b_1,b_2,\cdots ,b_k$。

输出格式

输出一行一个整数，为所求的答案$n$。

输入输出样例

输入样例 #1

3
1 2 3
2 3 5

输出样例 #1

23

说明/提示

对于$100\%$的数据：

$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}$。

每个测试点时限$1$秒。

注意：对于 C/C++ 语言，对$64$位整型数应声明为 long long。

若使用 scanf，printf 函数（以及 fscanf，fprintf 等），应采用 %lld 标识符。