题目内容

你正在设计一种数据压缩算法，处理一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。

你可以进行一种名为「基除」的操作：选择一个大于 $1$ 的元素 $x$，将其替换为 $\dfrac{x}{p}$，其中 $p$ 是 $x$ 的一个「基除数」。

一个大于 $1$ 的整数 $p$ 被称作 $x$ 的基除数，当且仅当 $p$ 整除 $x$ 且 $p$ 本身不能被任何大于 $1$ 且小于 $p$ 的整数整除（换句话说，$p$ 是一个既是 $x$ 的约数又是素数的数）。

你最多可以执行 $k$ 次基除操作，每次操作可以任意选择序列中的元素（同一元素可被操作多次）。你的目标是使得所有元素之和尽可能小，请求出在最优策略下这个最小和是多少。

约束：序列长度 $n$ 不超过 $2 \times 10^5$，操作次数 $k$ 不超过 $2 \times 10^5$，序列中的每个元素均为不超过 $10^6$ 的正整数。

输入描述

第一行包含两个整数 $n$ 和 $k$，分别表示序列的长度和允许的最大操作次数。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示初始序列。

输出描述

输出一个整数，表示经过最多 $k$ 次操作后，序列所有元素之和能达到的最小值。

样例1

输入

2 10
6 8

输出

2

说明

初始序列为 $[6, 8]$，总和为 $14$。 每个元素的「基除」操作路线由其最小素因子决定：

• 6 的最小素因子是 2，第一次操作变为 $6 / 2 = 3$，收益为 $6 - 3 = 3$；3 的最小素因子是 3，第二次操作变为 $3 / 3 = 1$，收益为 $3 - 1 = 2$。
• 8 的最小素因子是 2，依次变为 $8 \rightarrow 4 \rightarrow 2 \rightarrow 1$，对应的收益依次为 $4, 2, 1$。

使用大根堆贪心选取当前收益最大的操作：

• 第 1 次选择 8 的收益 4，和变为 $14 - 4 = 10$；
• 第 2 次选择 6 的收益 3，和变为 $10 - 3 = 7$；
• 第 3 次选择 4 的收益 2，和变为 $7 - 2 = 5$；
• 第 4 次选择 3 的收益 2，和变为 $5 - 2 = 3$；
• 第 5 次选择 2 的收益 1，和变为 $3 - 1 = 2$。

此后所有元素均已变为 1，无法继续操作。由于 $k = 10$ 远大于可操作次数，最终序列和为 2。

样例2

输入

3 2
9 4 6

输出

10

说明

初始序列为 $[9, 4, 6]$，总和为 $19$。 各元素的收益序列：

• 9 的最小素因子为 3，第一次收益 $9 - 9/3 = 6$，变为 3；后续 3 的收益为 $3 - 3/3 = 2$。
• 4 的最小素因子为 2，收益依次为 $4 - 4/2 = 2$（变为 2），以及 $2 - 2/2 = 1$（变为 1）。
• 6 的最小素因子为 2，第一次收益 $6 - 6/2 = 3$（变为 3），后续收益为 $2$（变为 1）。

$k=2$ 时，贪心选择：

• 第 1 次操作：当前最大收益为 9 的 6，执行后序列变为 $[3, 4, 6]$，和变为 $19 - 6 = 13$；
• 第 2 次操作：此时可选收益有 $3 \rightarrow 1$ 的 2、$4 \rightarrow 2$ 的 2 以及 $6 \rightarrow 3$ 的 3，最大为 3，选择 6 操作，序列变为 $[3, 4, 3]$，和变为 $13 - 3 = 10$。

操作次数用完，最终最小和为 10。

样例3

输入

1 0
100

输出

100

说明

序列只有一个元素 100，允许操作次数 $k = 0$。无法执行任何「基除」操作，因此序列和保持为初始值 100。