配点 : 100 点
問題文
黑板上 N 以下正整数是 1 一一写着。另外,M 正整数 给出了 x_1,\ldots,x_M 。在这里,i \neq j 如果 x_i 和 x_j 保证是不相交的。
您可以执行以下操作 您可以根据需要多次执行此操作 0 。
- 1 以上 M 的整数 声明 i 有一定的 x_i 的倍数 选择 y 。黑板上 如果写入 y ,则 选择 1 并 重写为\frac{y}{x_i} 。
运算结束后,求黑板上写的整数之和最小。
制約
- 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 不相交
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M x_1 \ldots x_M
出力
输出答案。
入力例 1
10 2 2 3
出力例 1
24
写入的整数为 如果从 (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) 变为。
入力例 2
2000000000 3 20 23 7
出力例 2
1597222223653885214