Prime Gift

题意翻译

题目描述 与格里沙的好行为相反,奥列格虽然有一整年的时间供他自由支配,但他在过去的一年里还是没有学会该如何解决数论问题,这就是为什么他不是被底但·莫罗兹(这是谁)拜访,而是被他的队友安德鲁拜访,安德鲁郑重地给他展示了N个截然不同的质数(一个集合)并交给他一个简单的任务: 奥列格需要找到第k小的整数,并把它的所有的素因子加入这个集合里。 输入输出格式 输入格式: 第一行包含一个整数n(1<=n<=16) 第二行包含n个按升序排列的不同的素数p1,p2,...,pn(2<=pi<=100) 最后一行给出了一个整数k(1 <= k)并保证第k个最小的整数在这个集合中的所有素因子不超过10^18 输出格式: 输出第k小的整数,保证答案范围不超过10^18。 说明: 样例一解释如下所示:(1,2,3,4,5,6,8,...) 列表中第七小的整数是8。 Translated by @Spencer

题目描述

Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of $ n $ distinct prime numbers alongside with a simple task: Oleg is to find the $ k $ -th smallest integer, such that all its prime divisors are in this set.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1<=n<=16 $ ). The next line lists $ n $ distinct prime numbers $ p_{1},p_{2},...,p_{n} $ ( $ 2<=p_{i}<=100 $ ) in ascending order. The last line gives a single integer $ k $ ( $ 1<=k $ ). It is guaranteed that the $ k $ -th smallest integer such that all its prime divisors are in this set does not exceed $ 10^{18} $ .

输出格式


Print a single line featuring the $ k $ -th smallest integer. It's guaranteed that the answer doesn't exceed $ 10^{18} $ .

输入输出样例

输入样例 #1

3
2 3 5
7

输出样例 #1

8

输入样例 #2

5
3 7 11 13 31
17

输出样例 #2

93

说明

The list of numbers with all prime divisors inside $ {2,3,5} $ begins as follows: $ (1,2,3,4,5,6,8,...) $ The seventh number in this list ( $ 1 $ -indexed) is eight.