← 返回题目列表

AtCoder · tenka1_2015_qualB_e

E. 天下一行动

中文机器翻译题面 查看原题

問題文

您正在玩一款名为 Tenkaichi Calculation 的游戏。 Tenkaichi操作定义如下。 小于或等于

  • 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