Problem Description

In a video game, a supercomputer called the “Central Core” controls the operation of the entire city. However, recently the Central Core was locked by a firewall made of malicious code, and the city has fallen into paralysis.

To break this firewall, you must enter a specific “unlock code”. This unlock code is not a simple number, but the $n$-th “valid number”. The city has $k$ special servers, and the $i$-th server comes with a unique key $p_i$. Any positive integer that is divisible by at least one of these $k$ keys can be considered a “valid number”.

Given $n$ and $p_1,p_2,\ldots ,p_k$, your task is to find the $n$-th “valid number”, use it as the unlock code, and enter it into the “Central Core” to save the city.

For example, if $n=10$, $k=3$, and the keys are $2, 3, 5$, then the numbers divisible by $2$, $3$, or $5$ are, in order, $2, 3, 4, 5, 6, 8, 9, 10, 12, 14\ldots$. The $10$-th number is $14$, so the answer is $14$.

Input Format

• $n$ means you need to find the $n$-th valid number.
• $k$ means the number of keys.
• $p_i$ means the value of the $i$-th key.

Output Format

• Output a positive integer $ans$, representing the $n$-th number that is divisible by at least one number among $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

Hint

Constraints

• $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}$。
• It is guaranteed that the required answer is $\le 10^{18}$.
• All input numbers are integers.

Scoring

This problem has four subtasks with the following constraints. Each subtask may contain one or more testdata files, and you will get the score for a subtask only if you answer all testdata in that subtask correctly.

Translated by ChatGPT 5