You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 最近沉迷某款自走棋游戏，该游戏最近开启了 "符文大陆" 版本。该版本游戏开始前，会随机抽签选择一个城邦，每个城邦都有不同的效果，在每回合游戏中玩家通过将各种棋子放到棋盘上组成强有力的羁绊，每一种羁绊都会有不同的效果。

在某局游戏中，欧皇小 Z 组成了一个非常强大的阵容，该阵容的效果是在每回合游戏中，会召唤 $n$ 个法术，法术编号为 $1,2,\dots,n$，其中第 $i$ 个法术有一个能力值 $a_i$。棋盘位置从 $1$ 开始顺序编号，能力值为 $a_i$ 的法术，可以保护所有编号满足 $x | a_i$ 的 $x$ 位置，其中 $x|a_i$ 表示 $x$ 整除 $a_i$，即 $x$ 是 $a_i$ 的因数。

• 例如，如果某一个法术 $a_i=12$，那么这个保护法术就可以保护 $1,2,3,4,6,12$ 这些位置。

小 Z 想要 "吃鸡"（得到第一名），他通过计算得到，游戏的每一个回合，他都需要将最厉害的棋子放在至少被 $m$ 个法术所保护的位置。同时，为了尽可能得接近对手的棋子，小 Z 又需要将这个棋子放在编号尽可能大的位置。

小 Z 想要知道棋子应该放在什么位置。

【注意】

两个法术保护的位置可能完全相同，即 $n$ 个法术中，有可能存在多个法术，他们的能力值是一样的。

输入格式

第一行两个整数 $n,m$，整数间用空格隔开。

接下来一行，$n$ 个整数 $a_1,a_2,\dots,a_n$，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个法术的能力值。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

3 2
3 4 5

样例输出 #1

1

样例 #2

样例输入 #2

5 3
3 6 4 8 12

样例输出 #2

4

提示

【样例 1 解释】

法术 $1$ 的能力值为 $3$，可以保护位置 $1,3$；
法术 $2$ 的能力值为 $4$，可以保护位置 $1,2,4$；
法术 $3$ 的能力值为 $5$，可以保护位置 $1,5$；
其中，至少被 $2$ 个法术保护的位置只有 $1$，所以答案为 $1$。

【样例 2 解释】

法术 $1$ 的能力值为 $3$，可以保护位置 $1,3$；
法术 $2$ 的能力值为 $6$，可以保护位置 $1,2,3,6$；
法术 $3$ 的能力值为 $4$，可以保护位置 $1,2,4$；
法术 $4$ 的能力值为 $8$，可以保护位置 $1,2,4,8$；
法术 $5$ 的能力值为 $12$，可以保护位置 $1,2,3,4,6,12$；
其中，至少被 $3$ 个法术保护的位置有 $1,2,3,4$，其中编号最大的为 $4$，所以输出答案 $4$。

【数据范围】

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

对于所有测试点，有 $1\le m \le n \le 5 \times 10^6,1 \le a_i \le 10^7$。各个测试点详细分布如下：