Xếp sách

Trong một thư viện nổi tiếng ở Tokyo, ban quản lý vừa nhận được một lượng lớn sách mới và cần phân loại chúng để sắp xếp lên các kệ sách. Thư viện có \(n\) kệ, mỗi kệ chứa một số lượng sách nhất định. Số lượng sách trên kệ thứ \(i\) được biểu thị bằng số nguyên \(a_i\).

Để hỗ trợ quá trình sắp xếp, ban quản lý thư viện đã thuê \(m\) đội nhân viên để đảm nhiệm công việc này. Các đội sẽ được giao nhiệm vụ sắp xếp sách trên các đoạn kệ liên tiếp, được chia bởi \(m-1\) điểm cắt \(k_1, k_2, \dots, k_{m-1}\) (\(k_0 = 0 < k_1 < \dots < k_{m-1} < k_m = n\)). Đội thứ \(i\) sẽ chịu trách nhiệm sắp xếp các kệ từ \(k_{i-1} + 1\) đến \(k_i\).

Mỗi đội nhân viên phải sắp xếp số sách trên các kệ trong đoạn được giao sao cho tất cả các kệ trong đoạn đều có cùng số lượng sách. Để làm điều này, đội nhân viên có thể thực hiện hai loại thao tác, mỗi thao tác mất đúng \(1\) đơn vị thời gian:

• Thao tác 1: Lấy một cuốn sách ra khỏi một kệ trong đoạn được giao.
• Thao tác 2: Thêm một cuốn sách mới vào một kệ trong đoạn được giao.

Thời gian để hoàn thành việc sắp xếp được tính bằng thời gian dài nhất mà một đội nhân viên mất để hoàn thành nhiệm vụ của mình. Yêu cầu là tìm cách chia các kệ thành \(m\) đoạn sao cho tổng thời gian sắp xếp là ít nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n, m\) \((1 \leq m \leq n \leq 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) \((0 \leq a_i \leq 10^6)\).

Kết quả:

• Ghi ra một số nguyên duy nhất là thời gian tối thiểu cần thiết để hoàn thành việc sắp xếp.

Ràng buộc:

• \(25\%\) số điểm: \(m = 1, n \leq 100\) và \(a_i \leq 100\).
• \(25\%\) số điểm: \(m = 2\) và \(n \leq 1000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.

Example

5 4
5 6 3 8 1

1

7 3
8 2 3 1 7 7 10

3