← 返回题目列表

AtCoder · codefestival_2016_ex_b

B. 准确付款

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

分数: 1500 点

问题陈述

高桥王国使用的货币是 迈恩。 有 1-, 10-, 100-, 1000- 和 10000-Myon 硬币,等等。正式来说,有 10^n-任何非负整数的 Myon 硬币 n.

有 N 商品在 Ex Store 出售。 的价格 i-th (1≦i≦N) 项目是 A_i 迈昂。

高桥将购买其中一些,至少一个,可能全部 N 项目。 他讨厌找零,所以他想带硬币去商店,这样无论他选择购买什么商品,都可以在不找零的情况下支付总价。 而且,由于硬币很重,他想带尽可能少的硬币。

找出他必须带去商店的最少硬币数量。可以假设他有无限的硬币供应。

约束

  • 1≦N≦20,000
  • 1≦A_i≦10^{12}

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_N

输出

打印高桥必须携带到商店的最低硬币数量,这样无论他选择购买什么商品,他都可以支付总价而无需找零。


示例输入 1

3
43 24 37

示例输出 1

16

有七种可能的总价格: 24, 37, 43, 61, 67, 80, 和 104。 与七个 1-Myon 硬币,八个 10-Myon 硬币和一枚 100-Myon 硬币,高桥可以支付其中任何一个,而无需找零。


示例输入 2

5
49735011221 970534221705 411566391637 760836201000 563515091165

示例输出 2

105