Rót đầy các thùng chứa (Fill the Containers)

Nguồn: UVa

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

Đề bài

Có $n$ bình sữa xuất hiện theo thứ tự trên băng chuyền. Bình thứ $i$ chứa đúng $c_i$ đơn vị sữa.

Toàn bộ sữa của một bình phải được rót nguyên vào đúng một thùng; không được chia sữa của cùng một bình cho nhiều thùng.

Đánh số các thùng từ $1$ đến $m$. Thứ tự trên băng chuyền phải được bảo toàn: nếu bình $i$ xuất hiện trước bình $j$ và chúng được rót lần lượt vào thùng $r$ và thùng $s$, thì phải có

Vì vậy, các bình được rót vào mỗi thùng tạo thành một đoạn liên tiếp của dãy ban đầu. Một số thùng có thể không được dùng.

Các thùng không bắt buộc có cùng dung tích. Ta được quyền chọn dung tích riêng cho từng thùng. Sau khi chuyển hết sữa, xét dung tích lớn nhất trong các thùng đã dùng. Hãy tìm giá trị nhỏ nhất có thể của dung tích lớn nhất đó.

Tương đương, hãy tìm số nhỏ nhất $C$ sao cho có thể chuyển hết sữa theo đúng thứ tự vào không quá $m$ thùng và tổng lượng sữa trong mỗi thùng không vượt quá $C$.

Input

Dòng đầu chứa $n,m$. Dòng sau chứa $c_1,\ldots,c_n$.

Output

In giá trị nhỏ nhất có thể của dung tích lớn nhất trong các thùng.

Subtask

• Subtask 1 — 20%: $m=1$ hoặc $m\ge n$.
• Subtask 2 — 30%: $1\le n\le100$.
• Subtask 3 — 50%: $1\le n\le1000$, $1\le m\le10^6$, $1\le c_i\le10^6$.

Ví dụ

Input

5 3
1 2 3 4 5

Output

6

Giải thích

Có thể rót các nhóm $[1,2,3]$, $[4]$, $[5]$ vào ba thùng. Dung tích lớn nhất là $6$ và không thể giảm hơn.