← 返回题目列表

Codeforces · 912/E

E. 优质礼物

中文机器翻译题面 查看原题

与 Grisha 的良好行为相反,Oleg 尽管他有一整年的时间可以支配,但在过去的一年里并没有学会如何解决数论问题。这就是为什么他的队友安德鲁而不是德德·莫罗兹拜访了他,安德鲁郑重地向他提供了一组 n 个不同的素数以及一个简单的任务:奥列格要找到第 k 个最小的整数,使得它的所有素数因子都在这个集合中。

输入

第一行包含一个整数 n (1 ≤ n ≤ 16)。

下一行按升序列出 n 个不同的素数 p1, p2, ..., pn (2 ≤ pi ≤ 100)。

最后一行给出一个整数 k (1 ≤ k)。保证其所有素因数都在该集合中的第 k 个最小整数不超过 1018。

输出

打印一行,其中包含第 k 个最小整数。保证答案不超过1018。

示例

输入 #1

3
2 3 5
7

输出 #1

8

输入 #2

5
3 7 11 13 31
17

输出 #2

93

注意

所有素因数都在 {2, 3, 5} 内的数字列表开始如下:

(1, 2, 3, 4, 5, 6, 8, ...)

该列表中的第七个数字(1 索引)是 8。