与 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。