E - 天下一演算 Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

あなたは天下一演算というゲームで遊んでいます。天下一演算は以下のように定義されます。

  • 1 以上 10^5 以下の整数 M、N と、0 以上 M 未満の整数 N 個からなる配列 A が与えられる。
  • 配列の全ての要素に 10 を掛ける操作を何回か行う。
  • その後、配列のある 1 つの要素に 1 を足す操作を何回か行う。
  • 全ての要素が M の倍数になるとクリアとなる。

例えば、M = 7、N = 4、A = \[0, 1, 2, 3\] のとき、全ての要素に 3 回 10 を掛けた後、2 番目の要素に 1 回 1 を足し、3 番目の要素に 2 回 1 を足し、4 番目の要素に 3 回 1 を足すと、A = \[0, 1001, 2002, 3003\] となり、合計 9 回の操作で全ての要素が M の倍数になります。

天下一演算をできるだけ少ない回数の操作でクリアしたときの、合計の操作回数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

M N
A_1
A_2
:
A_N
  • 1 行目には、2 つの整数 M (1 ≦ M ≦ 10^5)、N (1 ≦ N ≦ 10^5) が空白区切りで与えられる。
  • 2 行目からの N 行に、配列 A のそれぞれの要素 A_i (0 ≦ A_i < M) が与えられる。

出力

天下一演算をできるだけ少ない回数の操作でクリアしたときの、合計の操作回数を出力せよ。出力の末尾に改行を入れること。

配点

この問題には部分点は設定されていない。正解した場合は、130 点が与えられる。

入力例1

7 4
0
1
2
3

出力例1

9

問題文中で説明したケースです。

入力例2

1001 1
1

出力例2

4

3 回 10 を掛けた後、1 回 1 を足すと、M の倍数になります。

入力例3

1 2
0
0

出力例3

0

はじめから M の倍数です。

入力例4

12345 5
12
34
56
78
90

出力例4

1884