Mô tả và yêu cầu

Bước vào tiểu học, Bé Bi được cô giáo chủ nhiệm cho làm lớp trưởng. Nhân dịp kỷ
niệm ngày thành lập trường, Bé Bi tổ chức cho cả lớp chơi 1 trò chơi sau:
Có N đống sỏi xếp thành một hàng, đống thứ i có Ai viên sỏi. Ta có thể ghép hai đống
sỏi bất kỳ thành một đống và mất một chi phí bằng 5% tổng hai đống sỏi đó. Hãy tìm cách
ghép N đống sỏi này thành một đống với chi phí là nhỏ nhất.
Ví dụ: Nếu chúng ta có 4 đống sỏi với số lượng sỏi là 10, 11, 12 và 13.
- Bước 1: Ghép 2 đống 10 và 11 thành 1 đống có số lượng 21 (chi phí là 1.05)
- Bước 2: Ghép đống 21 vừa thu được với đống 12 thành đống có số lượng 33 (chi
phí 1.65)
- Bước 3: Ghép đống 33 vừa thu được với đống 13 thành 1 đống cuối cùng có số
lượng sỏi là 46 (chi phí 2.3)
- Vậy tổng chi phí là 5.00. Tuy nhiên đây không phải là phương án ghép đống tối ưu,
chúng ta có phương án ghép 4 đống này thành 1 đống với chi phí nhỏ nhất là 4.60.
Các bạn hãy tìm giúp Bé Bi phương án chơi tối ưu nhé!
Dữ liệu: vào từ thiết bị nhập chuẩn có dạng:
 Dòng 1: Số nguyên dương N (2 ≤ 𝑁 ≤ 100.000) là số đống sỏi.
 Dòng tiếp theo, ghi N số nguyên dương, tương ứng là số lượng sỏi trong từng đống.
Số lượng sỏi không vượt quá 10.000.
Kết quả: Đưa ra thiết bị xuất chuẩn chứa một số thực duy nhất là chi phí nhỏ nhất phải trả
để ghép N đống sỏi thành 1 đống. Kết quả ghi dưới dạng 2 chữ số sau dấu thập phân.

Ví dụ

INPUT                            OUTPUT

                 4                                   4.60

                 10 11 12 13

                 2                                   0.10

                 1 1