题目内容

小红是一个热爱数学的年轻数学家，他对数字和因子分解有着深入的研究。

有一天，他在一次偶然的探索中发现了一款神奇的游戏，名为“除数游戏”。

在这个游戏中，玩家需要在一个整数数组 $a$ 中选择一个大于1的数字 $a_i$ ，并将其除以其中一个素因子 $p$ （素因子是能被 $a_i$ 整除的素数）。接着，玩家可以继续将新数字除以素因子，直到进行了 $k$ 次操作。

小红很快就意识到，这个游戏可以为他的研究提供很多有用的信息。他开始探究在最多进行 $k$ 次操作的情况下，玩家能够通过该游戏达到的最小数组总和是多少？

输入描述

第一行输入两个正整数$n$和$k$，代表数组大小以及操作次数。

第二行输入$n$个正整数$a_i$，代表数组的元素。

$1≤n,k≤200000$

$1≤a_i≤10^6$

输出描述

一个整数，代表操作后的所有元素最小的和。

样例

输入

5 2
1 2 3 4 5

输出

9