Word Math

Interview

Time limit2sMemory limit256 MB

Summary

Assign distinct digits 0-9 to letters so that the sum of several words, read as base-10 numbers, is as large as possible.

Level: Medium4 of 10
Topics: Greedy, Math, Sorting
Solved: No attempts yet

Problem

Assign a distinct decimal digit from 0 to 9 to each different uppercase letter. The same letter must always use the same digit, and no two different letters may use the same digit.

After replacing the letters, each word is interpreted as a base-10 number. Choose the digit assignment that maximizes the sum of all given words, and output that maximum sum.

Input

The first line contains the number of words N (1 <= N <= 10).

Each of the next N lines contains one word. Every word consists only of uppercase English letters. Across all words, at most 10 different letters appear, and each word has length at most 8. Different letters represent different digits.

Output

Print the maximum possible sum of the given words.

Examples4

Example 1
Input
```
2
AAA
AAA
```
Expected output
```
1998
```
Example 2
Input
```
2
GCF
ACDEB
```
Expected output
```
99437
```
Example 3
Input
```
10
A
B
C
D
E
F
G
H
I
J
```
Expected output
```
45
```
Example 4
Input
```
2
AB
BA
```
Expected output
```
187
```