Sao chép sách (Copying Books)

Nguồn: UVa

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

Đề bài

Có $m$ quyển sách theo thứ tự $1,2,\ldots,m$. Quyển $i$ có $p_i$ trang. Cần chia toàn bộ sách cho đúng $k$ người chép, với các điều kiện:

• mỗi quyển thuộc đúng một người;
• mỗi người nhận ít nhất một quyển;
• các quyển của mỗi người tạo thành một đoạn liên tiếp trong thứ tự ban đầu.

Khối lượng công việc của một người là tổng số trang được giao. Thời gian hoàn thành do người có khối lượng lớn nhất quyết định.

Hãy tìm giá trị nhỏ nhất có thể của

$$\max_{1\le j\le k} \text{(tổng trang giao cho người }j\text{)}.$$

Bản PHOJ chỉ yêu cầu in giá trị tối ưu, không yêu cầu in vị trí các dấu chia.

Input

• Dòng đầu chứa $m,k$.
• Dòng thứ hai chứa $p_1,p_2,\ldots,p_m$.

Output

In tổng trang lớn nhất nhỏ nhất có thể.

Subtask

• Subtask 1 — 20%: $m\le30$.
• Subtask 2 — 30%: $m\le200$.
• Subtask 3 — 50%: $1\le k\le m\le500$, $1\le p_i<10^7$.

Ví dụ

Input

9 3
100 200 300 400 500 600 700 800 900

Output

1700

Giải thích

Một phân hoạch tối ưu là $[100,200,300,400,500]$, $[600,700]$, $[800,900]$, có tổng lần lượt $1500,1300,1700$. Không thể làm giá trị lớn nhất nhỏ hơn $1700$.