Problem Description

In the Kingdom of Takahashi, the currency unit is "Myon". In the Kingdom of Takahashi, coins with denominations of powers of $10$ ($1, 10, 100, 1000, ...$) are used.

At the Exibi Shop, $N$ items are on sale. The price of item $i$ ($1 \leq i \leq N$) is $A_i$ Myon.

Takahashi-kun is going to the Exibi Shop and plans to buy between $1$ and $N$ items. Takahashi-kun hates getting change, so he wants to choose the coins to put in his wallet such that no change is given for any purchase. Also, he wants to keep the number of coins as few as possible due to the weight of the wallet.

Determine the minimum number of coins Takahashi-kun needs to put in his wallet to ensure no change is given for any purchase. Assume that there will never be a shortage of coins for the purpose of putting them in the wallet.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the minimum number of coins that need to be put in the wallet to ensure no change is given for any purchase.

Sample Input and Output

Sample Input #1

3
43 24 37

Sample Output #1

16

Sample Input #2

5
49735011221 970534221705 411566391637 760836201000 563515091165

Sample Output #2

105

Notes/Hints

Constraints

• $1 \leq N \leq 20,000$
• $1 \leq A_i \leq 10^{12}$

Sample Explanation 1

The possible amounts to pay are $24, 37, 43, 61, 67, 80, 104$. With $7$ coins of $1$ Myon, $8$ coins of $10$ Myon, and $1$ coin of $100$ Myon, these amounts can be paid without change.

见题面 Input 部分

见题面 Output 部分