Mô tả bài toán

Cho dãy số ~ A ~ gồm ~ N ~ số nguyên dương. Chia dãy ~ A ~ thành ~ K ~ dãy con gồm các số liên tiếp. Gọi:

• ~ F[i] = A[p[i - 1] + 1] + A[p[i - 1] + 2] + \ldots + A[p[i]~ với ~ 1 \leq i \leq k ~, là tổng của đoạn ~ i ~.
• ~ p[0] = 0 ~, ~ p[k] = N ~, và ~ 1 \leq p[1] < p[2] < \ldots < p[k - 1] < N ~.
• ~ S = \max(F[i]) ~ với ~ 1 \leq i \leq k ~.

Nhiệm vụ: Chia dãy ~ A ~ thành ~ K ~ dãy con sao cho giá trị ~ S ~ nhỏ nhất có thể.

Input:

• Dòng đầu tiên chứa hai số nguyên ~ N, K ~ (~ 1 \leq K \leq N \leq 10^5 ~).
• Dòng thứ hai chứa ~ N ~ số nguyên ~ A[1], A[2], \ldots, A[N] ~ (~ 1 \leq A[i] \leq 10^4 ~).

Output:

• Ghi một số nguyên duy nhất là giá trị nhỏ nhất ~ S ~ có thể đạt được.

Ví dụ:

Input:

5 3
3 2 4 2 5

Output:

6

Giải thích ví dụ:

• Chia dãy thành các đoạn: ~[3], [2, 4], [2, 5]~.
• Tổng của từng đoạn là ~ F[1] = 3, F[2] = 6, F[3] = 7 ~.
• Giá trị lớn nhất ~ S = \max(F[i]) = 6 ~, là nhỏ nhất có thể đạt được.