After a long day of school, you are now back at your house. Preharps inspired by 0xBADF00D, you decided that your dinner needs to be good. You found out your food and toppings have actually more dimensions than you thought, its not as simple as $a$ times $b$. You are now back to the drawing board for G00DF00D.

You have $N$ food items, they each have a food value of $a_i$. When you combine two food items together, you create a dish with value described as follows:

1. Prefix both values with zeros, so that they both have 8 digits.
2. Take the first digit of both numbers, multiply them.
3. Do this for all digits.
4. The resulting dish value is the sum of those products.

Find the maximum possible sum of all dish values. $N$ is guaranteed to be even, so no food will be wasted.

Input

The first line contains an integer $N$.
The second line contains $N$ integers, the food values $a_i$.

Output

Output the maximum possible sum of all dish values.

Constraints

For all test cases: $2 \le N \le 20, 1 \le a_i \lt 10^8$ ($a_i$ have 8 or fewer digits), $n$ even.
Subtask 1 (10%): $N = 2$
Subtask 2 (40%): $N \le 10$
Subtask 3 (49%): $N \le 16$
Subtask 4 (1%): No other constraints