[TJOI2009]猜数字

题目描述

现有两组数字,每组 $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``` 标识符。