Cho một dãy gồm hỗn hợp. Mỗi hỗn hợp có một màu sắc nhất định. Khi trộn hai hỗn hợp, ta sẽ thu được một hỗn hợp mới và tạo ra một lượng khói.
Lượng khói tạo ra khi trộn hai hỗn hợp có màu và là .
Màu của hỗn hợp mới là .
Thứ tự các hỗn hợp trong dãy là cố định. Bạn chỉ có thể trộn hai hỗn hợp liền kề nhau.
Ví dụ, nếu bạn có các hỗn hợp , bạn có thể trộn và trước. Dãy sẽ trở thành , trong đó là hỗn hợp mới.
Yêu cầu: Hãy tìm cách trộn tất cả các hỗn hợp thành một hỗn hợp duy nhất sao cho tổng lượng khói tạo ra là nhỏ nhất.
Dữ liệu:
Một dòng chứa số nguyên .
Một dòng chứa số nguyên là màu của hỗn hợp.
Kết quả: Một dòng duy nhất chứa số nguyên là tổng lượng khói tối thiểu.
Ví dụ:
Dữ liệu:
2
18 19
Kết quả:
342
Dữ liệu:
3
40 60 20
Kết quả:
2400
Giải thích:
Trường hợp 1: Có 2 hỗn hợp màu 18 và 19. Khói tạo ra là .
Trường hợp 2: Có 3 hỗn hợp màu 40, 60, 20. Có thể trộn 40 và 60 trước, sau đó trộn với 20. Tổng khói là .
