题目描述

在一電玩遊戲裡，有一個被稱為「中央核心」的超級電腦控制著整個城市的運作。然而，最近中央核心被一道由惡意程式碼組成的防火牆鎖住，城市陷入了癱瘓。

要解開這道防火牆，必須輸入一個特定的「解鎖碼」。這個解鎖碼不是一個簡單的數字，而是第 $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	無額外限制。