Bạn có sợi dây với độ dài khác nhau. Chi phí để nối hai sợi dây lại với nhau bằng tổng độ dài của chúng. Hãy tìm cách nối tất cả sợi dây này thành một sợi duy nhất sao cho tổng chi phí nối là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa số nguyên .
Dòng thứ hai chứa số nguyên là độ dài của mỗi sợi dây.
Kết quả: Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ:
Dữ liệu:
4
4 3 2 6
Kết quả:
29
Giải thích:
Nối 2 và 3, chi phí là 5. Các sợi dây còn lại: 4, 6, 5.
Nối 4 và 5, chi phí là 9. Các sợi dây còn lại: 6, 9.
Nối 6 và 9, chi phí là 15.
Tổng chi phí: .
Giới hạn:
.
Độ dài mỗi sợi dây là một số nguyên dương không vượt quá .
