Problem
Jack Đẹp trai muốn thành lập nhà máy chế biến Eridium của riêng mình.
Có n nhà máy dưới sự kiểm soát của Jack, mỗi nhà máy được đánh số từ 1 đến n. Mỗi nhà máy được đặt tại mỏ Eridium, nơi nó cũng được khai thác kết hợp. Và số nhà máy càng cao thì càng mới.
Mỗi nhà máy có chỉ số hiệu quả a
i. Nó có thể dương, âm hoặc bằng không.
Mỗi nhà máy phải xử lý quặng Eridium. Bạn có thể sử dụng tiền gửi của riêng mình hoặc lấy quặng, được xử lý trước đây bởi một nhà máy khác, thông qua đường ống. Tuy nhiên, quá trình này có phần hạn chế. Thứ nhất, để không làm quá tải hệ thống đường ống, mỗi nhà máy có thể nhận quặng để xử lý tiếp theo một cách nghiêm ngặt của nhau (hoặc không nhận và sử dụng tiền gửi của chính mình). Thứ hai, các nhà máy cũ không có khả năng tái chế quặng về mặt kỹ thuật sau một nhà máy mới hơn.
Hiệu suất cuối cùng của toàn bộ hệ thống được tính như sau: đối với mỗi nhà máy, hiệu suất a
i của nó được lấy và nhân với giai đoạn xử lý, được tính bằng số lần quặng đầu vào được xử lý (để biết thêm chi tiết, xem phần giải thích cho các ví dụ), sau đó tất cả các giá trị thu được được tóm tắt cho tất cả các loại cây.
Hãy giúp Handsome Jack tổ chức hệ thống sao cho hiệu suất chung của toàn bộ hệ thống là cao nhất có thể.
Đầu vào:
Dòng đầu tiên ghi số tự nhiên n (1 <= n <= 7) - số lượng nhà máy.
Dòng thứ hai chứa n số nguyên cách nhau bởi dấu cách, trong đó số thứ i là a
i (-1000 <= a
i <= 1000) - hiệu suất cơ số của nhà máy theo số i.
Đầu ra:
In một số duy nhất - tổng hiệu suất tối đa có thể có của toàn bộ hệ thống.
Ví dụ:
| Đầu vào |
Đầu ra |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Giải thích:
Trong ví dụ đầu tiên, nhà máy đầu tiên khai thác quặng của chính mình sẽ có lợi nhất, nhà máy thứ hai nhận quặng từ nhà máy thứ nhất và nhà máy thứ ba nhận quặng từ nhà máy thứ hai. Trong trường hợp này, nhà máy thứ nhất thực hiện chế biến sơ cấp và năng suất của nó là 1 * 1 = 1. Nhà máy thứ hai thực hiện chế biến thứ cấp, năng suất của nó là 5 * 2 = 10. Và nhà máy thứ ba xử lý quặng nhận được lần thứ ba, vì vậy năng suất của nó là 3 * 3 = 9. Tổng hiệu suất là 1 + 10 + 9 = 20.
Xin lưu ý rằng trong ví dụ này, cây thứ hai và cây thứ ba không thể hoán đổi cho nhau, bởi vì nhà máy thứ hai sẽ không thể xử lý quặng sau nhà máy thứ ba vì lý do kỹ thuật vì nó cũ hơn nhà máy thứ ba.
Trong ví dụ thứ hai, nhà máy thứ nhất và thứ ba sẽ sử dụng tiền gửi của họ và nhà máy thứ hai sẽ nhận quặng từ nhà máy thứ nhất.