该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

众所周知，lzh 很喜欢玩游戏，而玩游戏自然要成为最强的那个人！

所以 lzh 的每件装备都非常强，他总共有 n 件装备，每一件装备都有对应的战力值，游戏角色的总战力就是装备的战力和

而今天游戏突然更新了一个新的版本，这个版本更新了一个新的特殊战力榜，这个特殊战力榜上的特殊战力并不是简单的将装备战力相加，而是全身所有装备战力的最大公约数

但是 lzh 的装备战力值都是参差不齐的，虽然每件装备的战力都很高，可它们的最大公约数非常小，甚至直接就是 1

这可急坏了 lzh ，他希望可以制霸服务器，那自然要在两个战力榜上都拿到第一！

为了吸引 lzh 这样的玩家氪金，于是游戏在第二天更新了特殊附魔系统，这个附魔系统很有趣，它允许你给你的装备附魔，而附魔的效果则是在计算特殊战力时减少某件装备的战力值。

对于每件装备，每附魔一次可以使这件装备的附魔等级 + 1 ，而每件装备的附魔等级是无限制的

例如 lzh 有三件装备，战力值分别为 7,3,4，如果给第一件和第三件装备附魔 1 次，那么在计算特殊战力时这三件装备的战力值分别为 6,3,3 可以得到特殊战力为 3

现在 lzh 的零花钱最多只够他进行 m 次附魔，请问 lzh 可以得到的最大特殊战力值是多少？

输入格式

第一行有两个整数 n,m，表示总共有 n 件装备，最多可以附魔 m 次

第二行有 n 个整数，分别表示每一件装备的战力值。

对于 50% 的数据：n <= 100000, a_i <= 1000000, k <= 10^9

对于 100% 的数据：n <= 1000000, a_i <= 1000000, k <= 10^9

输出格式

输出一个整数，表示 lzh 可以得到的最大特殊战力值。

样例

6 11
5 6 7 8 9 10

5

提示

附魔后每件装备的战斗力为 [5,5,5,5,5,10] 最大公约数为 5