Cho một mảng gồm \(N\) số nguyên dương. Hãy chia mảng này thành đúng \(K\) mảng con liên tiếp (mỗi phần tử của mảng ban đầu phải thuộc về đúng một mảng con) sao cho tổng lớn nhất của các mảng con là nhỏ nhất có thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le N \le 10^5\), \(1 \le K \le N\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng lớn nhất nhỏ nhất của mảng con sau khi chia.

Ví dụ

Đầu vào:

5 3
2 4 7 3 5

Đầu ra:

8

Giải thích: Chia mảng thành 3 mảng con liên tiếp: [2, 4], [7], [3, 5].

• Tổng mảng con thứ nhất: \(2 + 4 = 6\).
• Tổng mảng con thứ hai: \(7\).
• Tổng mảng con thứ ba: \(3 + 5 = 8\). Tổng lớn nhất của các mảng con là \(8\). Đây là cách chia tối ưu nhất.