AT_maximum_cup_2023_c 黒板

黑板上写有 $N$ 以下的所有正整数，各写一次。此外，给定 $M$ 个正整数 $x_1, \ldots, x_M$。保证当 $i \neq j$ 时，$x_i$ 和 $x_j$ 互质。 你可以进行如下操作任意多次（0 次也可以）： - 选择一个 $1$ 到 $M$ 之间的整数 $i$，以及某个 $x_i$ 的倍数 $y$。如果黑板上写有 $y$，则将其中一个 $y$ 改写成 $\frac{y}{x_i}$。 请你求操作后黑板上所有整数的和的最小值。

输入以如下格式从标准输入读入。 > $N$ $M$ $x_1$ $\ldots$ $x_M$

请输出答案。

### 样例解释 1 黑板上原有的整数为 $(1,2,3,4,5,6,7,8,9,10)$，可以按如下方式操作，使总和最小为 $24$： - $i=1, y=2$。黑板变为 $(1,1,3,4,5,6,7,8,9,10)$。 - $i=2, y=9$。黑板变为 $(1,1,3,4,5,6,7,8,3,10)$。 - $i=2, y=3$。黑板变为 $(1,1,1,4,5,6,7,8,3,10)$。 - $i=1, y=8$。黑板变为 $(1,1,1,4,5,6,7,4,3,10)$。 - $i=1, y=10$。黑板变为 $(1,1,1,4,5,6,7,4,3,5)$。 - $i=2, y=3$。黑板变为 $(1,1,1,4,5,6,7,4,1,5)$。 - $i=2, y=99$。黑板变为 $(1,1,1,4,5,6,7,4,1,5)$。 - $i=1, y=4$。黑板变为 $(1,1,1,2,5,6,7,4,1,5)$。 - $i=1, y=2$。黑板变为 $(1,1,1,1,5,6,7,4,1,5)$。 - $i=1, y=6$。黑板变为 $(1,1,1,1,5,3,7,4,1,5)$。 - $i=2, y=3$。黑板变为 $(1,1,1,1,5,1,7,4,1,5)$。 - $i=1, y=4$。黑板变为 $(1,1,1,1,5,1,7,2,1,5)$。 - $i=1, y=2$。黑板变为 $(1,1,1,1,5,1,7,1,1,5)$。 # 数据范围 - $1 \leq N \leq 2 \times 10^9$ - $1 \leq M \leq 300$ - $1 \leq x_i \leq 2 \times 10^9$ - $i \neq j$ 时，$x_i$ 和 $x_j$ 互质 - 输入均为整数 由 ChatGPT 5 翻译