問題文

黒板に 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 は互いに素
• 入力はすべて整数

入力例 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