#P2527. [SHOI2001] Panda的烦恼

[SHOI2001] Panda的烦恼

题目描述

panda 是个数学怪人,他非常喜欢研究跟别人相反的事情。最近他正在研究筛法,众所周知,对一个范围内的整数,经过筛法处理以后,剩下的全部都是质数,不过 panda 对这些不感兴趣,他只对被筛掉的数感兴趣,他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密,只是人们还没有发现罢了。

panda 还觉得如果只是单纯地从小到大筛的话,还不足够发现其中的奥秘,于是他决定对至多只包含某些质因数的数进行研究(比如说至多只包含质因数 2,32,3 的数有 2,3,4,6,8,9,2,3,4,6,8,9,\ldots),他需要得到这些数中第 kk 小的数( kk 是 panda 认为的宇宙系数),请你编个程序,帮助他找到这个数。

输入格式

第一行有两个整数 n,kn,knn 代表质因数的个数, kk 代表那个宇宙系数。

第二行有 nn 个整数,代表这 nn 个质因数,设这些质因数组成的序列为 pp

输出格式

仅一行,即至多只包含这 nn 个质因数的数中第 kk 小的正整数,设这个答案为 ansans

2 7
3 5
45

提示

样例解释

前六个数分别是 3,5,9,15,25,273,5,9,15,25,27

数据范围及限制

对于所有数据,有 1n1001\le n\le 1001k1051\le k\le 10^5piprimep_i\in\text{prime}pi103p_i\le 10^3pipj(ij)p_i\not=p_j(i\not=j)1ans2×1091\le ans\le 2\times 10^9