Đất nước K gồm thành phố, được đánh số từ 1 đến . Căn cứ vào vị trí địa lý của từng thành phố, chính phủ đã xác định độ quan trọng cho từng thành phố. Cụ thể, thành phố thứ có độ quan trọng là .
Để quá trình giao thương giữa các thành phố diễn ra thuận lợi, chính phủ đã quyết định xây dựng một hệ thống đường sắt nối liền các thành phố. Kết quả khảo sát cho thấy rằng, chi phí để xây dựng tuyến đường sắt nối liền hai thành phố và là .
Chính phủ cần chọn ra một số tuyến đường sắt để xây dựng, sao cho hai thành phố bất kì đều có thể đi đến nhau thông qua các tuyến đường sắt được xây, và tổng chi phí xây dựng các tuyến đường sắt là nhỏ nhất có thể. Từ thành phố có thể đi được đến thành phố nếu tồn tại một chuỗi thành phố sao cho có tuyến đường sắt trực tiếp giữa hai thành phố liên tiếp và với mọi .
Yêu cầu: Hãy giúp chính phủ xác định tổng chi phí nhỏ nhất để xây dựng hệ thống đường sắt trên.
Dữ liệu:
Dòng đầu tiên gồm một số nguyên () — số thành phố của đất nước K.
Dòng thứ hai gồm số nguyên () — độ quan trọng của thành phố .
Kết quả: Một số nguyên duy nhất là tổng chi phí xây dựng nhỏ nhất có thể.
Ví dụ:
Dữ liệu:
4
3 5 11 9
Kết quả:
3
Dữ liệu:
3
5 15 45
Kết quả:
0
Giải thích:
Ở ví dụ thứ nhất, ta cần xây dựng các tuyến đường sắt (1,2), (1,4) và (2,3) với chi phí lần lượt là 2, 0 và 1. Tổng chi phí là .
Ở ví dụ thứ hai, chi phí xây dựng đường sắt giữa hai thành phố bất kì luôn bằng 0. Do đó, tổng chi phí xây dựng là 0.
