询问第K小的数

题目描述

给你 $n$ 个互不相同的素数 $p_1,p_2,\cdots,p_n$，它们组成一个集合 $P$。

请你求出第 $k$ 小的正整数，满足：

• 该数字的所有素因子 $\in P$

$1\le n\le 16, 2\le p_i\le 100,$ 保证答案不超过 $10^{18}$。

注意：空集是任何集合的子集。

输入格式

第一行输入整数$n$（$1<=n<=16$）。

第二行输入$n$不同的质数$p_{1}, p_{2}, ... ,p_{n}$（$2<=p_{i}<=100$）。

最后一行输入一个整数$k$（$1<=k$），你所要求的即满足其所有质因子数均在此集合中的第$k$个小整数。

输出格式

输出集合中第$k$小的正整数，保证最终答案不超过$10^{18}$。

样例 #1

样例输入 #1

3
2 3 5
7

样例输出 #1

8

样例 #2

样例输入 #2

5
3 7 11 13 31
17

样例输出 #2

93

提示

所有质因子都在${2,3,5}$集合内的数如下所示：

$（1,2,3,4,5,6,8，…）$

其中的第七小的数字（下标为从$1$开）是8。

对于30%的数据， 保证最终答案不超过$10^{8}$。

对于100%的数据，$n$ ( $1<=n<=16$ )，$2<=p_{i}<=100$，$k$ ( $1<=k$ )，保证最终答案不超过$10^{18}$。