Commercial Calculator
QISAC has launched a new version of a calculator that charges users for performing arithmetic operations. The cost of each operation is calculated as 5% of the result of that operation, measured in dollars.
You are tasked with calculating the sum of N natural numbers using this calculator. Interestingly, the sequence in which you add these numbers can influence the total cost of the calculation, which deviates from the traditional principle that the sum remains unchanged regardless of the order of addends.
For instance, consider adding the numbers 10, 11, 12, and 13. If you add 10 and 11 first (costing $1.05), then add the result to 12 (costing $1.65), and finally add 13 (costing $2.3), the total cost would be $5. However, if you first add 10 and 11 (costing $1.05), then add 12 and 13 (costing $1.25), and finally add the two results together (costing $2.3), the total cost would be only $4.6.
Your task is to write a program that calculates the minimum cost required to sum these N numbers.
Input
The input begins with the number N (2 ≤ N ≤ 100000). This is followed by N natural numbers, each not exceeding 10000.
Output
Output the minimum amount of money needed to compute the sum of these N numbers, with a precision of at least 10^{-6}.