AT_maximum_cup_2023_c 黒板

黒板に $ 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} $ に書き換える。 操作後に黒板に書かれている整数の総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ x_1 $ $ \ldots $ $ x_M $

答えを出力せよ。

### Sample Explanation 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) $ となる。 ### Constraints - $ 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 $ は互いに素 - 入力はすべて整数