Đề bài
Tỷ phú Vương Lượng muốn xây dựng một thủy cung để thu hút khách du lịch cho làng Đông Bích. Anh ta đã mua \(n\) chú cá và \(m\) bể thủy sinh. Mỗi chú cá thứ \(i\) có sức mạnh là \(a_i\).
Vương Lượng cần phân chia các chú cá vào các bể thủy sinh. Tuy nhiên, các chú cá trong cùng một bể có thể kìm hãm nhau. Mức độ bất ổn của một chú cá được định nghĩa là tổng sức mạnh của tất cả các chú cá trong cùng bể với nó, bao gồm cả bản thân chú cá đó.
Bạn hãy giúp Vương Lượng sắp xếp các chú cá vào các bể sao cho tổng độ bất ổn của tất cả các chú cá là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(m \leq n \leq 2000\)): số lượng chú cá và số lượng bể thủy sinh.
- Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\)): sức mạnh của từng chú cá.
Dữ liệu ra
- Một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất có thể đạt được.
Giới hạn
| Subtask | Tỉ lệ | Ràng buộc |
|---|---|---|
| 1 | 20% | \(n \leq 8\) |
| 2 | 20% | \(n \leq 15\) |
| 3 | 20% | \(m = 2\) |
| 4 | 30% | \(n \leq 100\) |
| 5 | 10% | Không có giới hạn gì thêm |
Sample Input 1
6 3
9 2 11 3 5 8
Sample Output 1
75
Sample Input 2
4 4
10 20 30 40
Sample Output 2
100
Giải thích
Ví dụ 1: Một cách chia tối ưu: - Bể 1: cá thứ 1 và 6 (tổng sức mạnh 17) - Bể 2: cá thứ 2, 4, 5 (tổng sức mạnh 10) - Bể 3: cá thứ 3 (tổng sức mạnh 11)
Tổng độ bất ổn là \(17 + 17 + 10 + 10 + 10 + 11 = 75\)
Ví dụ 2: Mỗi chú cá được đặt vào một bể riêng biệt, nên tổng độ bất ổn là \(10 + 20 + 30 + 40 = 100\)