题目描述

与 Grisha 的良好表现相反，Oleg 尽管有整整一年的时间，却没能学会如何解决数论问题。因此，在过去的一年里，拜访他的不是 Ded Moroz，而是他的队友 Andrew。Andrew 隆重地送给他 $n$ 个互不相同的质数，并附上一道简单的任务：Oleg 需要找到第 $k$ 小的正整数，使得它的所有质因子都只来自于这 $n$ 个质数。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 16$）。

第二行包含 $n$ 个互不相同、按升序排列的质数 $p_1, p_2, ..., p_n$（$2 \leq p_i \leq 100$）。

最后一行给出一个整数 $k$（$1 \leq k$）。保证第 $k$ 小且所有质因子都仅来自这些质数的整数不超过 $10^{18}$。

输出格式

输出一行，即符合条件的第 $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 开始编号）是 $8$。

由 ChatGPT 5 翻译