说明

在一电玩游戏里，有一个被称为「中央核心」的超级电脑控制着整个城市的运作。然而，最近中央核心被一道由恶意代码组成的防火墙锁住，城市陷入了瘫痪。

要解开这道防火墙，必须输入一个特定的「解锁码」。这个解锁码不是一个简单的数字，而是第 $n$ 个「有效数字」。这座城市共有 $k$ 台特殊的服务器，其中第 $i$ 台服务器带有一个独特的密钥 $p_i$。任何一个正整数，只要能被这 $k$ 个密钥中的至少一个整除，就可以被视为一个「有效数字」。

给定 $n$ 和 $p_1,p_2,\ldots ,p_k$，你的任务是找出第 $n$ 个「有效数字」，将其作为解锁码输入「中央核心」，以拯救这座城市。

举例来说，若 $n=10$、$k=3$ 且密钥为 $2, 3, 5$。则因为能被 $2, 3$ 或 $5$ 整除的数依次是 $2, 3, 4, 5, 6, 8, 9, 10, 12, 14\ldots$，而第 $10$ 个数是 $14$，因此所求为 $14$。

输入格式

$$\begin{aligned} &n \; k \\ &p_1 \; p_2 \; \dots \; p_k \end{aligned}$$

• $n$ 代表你要找出第 $n$ 个有效数字。
• $k$ 代表密钥的个数。
• $p_i$ 代表第 $i$ 把密钥的数值。

输出格式

$$ans$$

• 输出一个正整数 $ans$，表示第 $n$ 个能被 $p_1,p_2,\ldots ,p_k$ 中至少一个数整除的数字。

10 3
2 3 5

14

5 2
4 6

16

1000000000 4
1806 1110 600 777767777

325960839000

提示

数据限制

• $1 \le n \le 10^9$。
• $1 \le k \le 6$。
• $1 \le p_1\times p_2\times\cdots\times p_k \le 10^{18}$。
• 保证所求答案 $\le 10^{18}$。
• 输入的数皆为整数。

评分说明

本题共有四组子任务，条件限制如下所示。每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	2	保证所求答案 $\le 10^{6}$。
2	27	$n \le 10, k \le 2$。
3	34	$n \le 10^5$。
4	37	无额外限制。