D.符文(beyond)

题目描述

你有一个数轴，数轴上所有整数的位置有一只青蛙。

小 L 喜欢吃青蛙，青蛙瑟瑟发抖。

有 $n$ 个符文，第 $i$ 个符文可以保护所有坐标为 $A_i$ 的因数的位置的青蛙。包括 $1$ 和 $A_i$ 。

传说一只青蛙如果被至少 $m$ 个符文保护，则这只青蛙是救世主。

你需要求出一个最大的自然数 $k$，使得 $k$ 这个位置的青蛙至少被 $m$ 个符文保护，保证有解。

输入格式

第一行两个自然数 $n,m$ 。

接下来一行 $n$ 个自然数 $A_i$ 。

输出格式

一行一个自然数，表示答案。

样例

输入样例 $1$

3 2
3 4 5

输出样例 $1$

1

输入样例 $2$

5 3
3 6 4 8 12

输出样例 $2$

4

输入样例 $3$

20 10
49 66 30 90 55 93 40 60 65 53 70 99 45 50 45 30 42 70 89 99

输出样例 $3$

5

数据范围

本题共 $20$ 个测试点 ，每个测试点 $5$ 分。

测试点编号	$n$ 的上限	$m$ 的上限	$A_i$ 的上限
$1$	$20$	$1$	$100$
$2\sim4$		$20$
$5$	$1000$	$2$	$1000$
$6\sim8$		$1000$
$9\sim 10$			$10^5$
$11\sim 14$	$10^5$
$15\sim18$	$10^6$		$10^7$
$19\sim 20$	$5\times 10^6$

对于所有测试点，$1\leq m\leq n\leq 5\times 10^6,1\leq A_i\leq 10^7$ 。

时间限制 : 4000 ms

空间限制 : 512 MB