分数: 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