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

Ôn lại truyền thống trò chơi dân gian, học sinh các trường THPT đã thành lập
ra CLB “Trò chơi dân gian”, mỗi thành viên trong CLB sẽ có trách nhiệm sưu tầm
và tổ chức trò chơi đó, Khánh là một thành viên của CLB đồng thời là HSG môn tin
với tối chất của một lập trình viên Khánh có một trò chơi như 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.
Các bạn hãy Khánh đưa ra phương án chơi tối ưu nhé!
Input: 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 t rong từng
đống. Số lượng sỏi không vượt quá 10.000.
Output: Đưa ra thiết bị xuất chuẩn có dạng:
• Ghi 1 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
Ràng buộc:
    •  Có 50% số test còn lại ứng với 40% số điểm của bài có 𝑁 ≤ 103.
    •  Có 50% số test còn lại ứng với 40% số điểm của bài có 𝑁 ≤ 105.