Chia mảng (Array Division)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $n$ số nguyên dương. Hãy chia mảng thành đúng $k$ đoạn con liên tiếp, không rỗng, phủ hết mảng.

Nếu tổng của đoạn thứ $j$ là $S_j$, giá trị của cách chia là:

Hãy tìm giá trị nhỏ nhất có thể của đại lượng này.

Input

Dòng đầu chứa $n,k$. Dòng sau chứa $x_1,\ldots,x_n$.

Output

In giá trị nhỏ nhất có thể của tổng lớn nhất trong $k$ đoạn.

Subtask

• Subtask 1 — 20%: $k=1$ hoặc $k=n$.
• Subtask 2 — 30%: $1\le n\le2000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le k\le n$, $1\le x_i\le10^9$.

Ví dụ

Input

5 3
2 4 7 3 5

Output

8

Giải thích

Một cách chia tối ưu là $[2,4]$, $[7]$, $[3,5]$ với các tổng $6,7,8$, nên giá trị lớn nhất là $8$.