Có n cuốn sách xếp thành hàng, cuốn thứ i dày ai trang. Cần chia hàng sách thành đúng k đoạn liên tiếp (mỗi đoạn có ít nhất một cuốn) cho k bạn đọc. Hãy chia sao cho số trang của đoạn nhiều trang nhất là nhỏ nhất có thể, và in ra số trang đó.
Minh họa chia hàng sách
Dữ liệu vào
Dòng đầu chứa n và k. Dòng thứ hai chứa n số nguyên dương a1…an.
Kết quả
Số trang nhỏ nhất có thể của đoạn nhiều trang nhất.
Giới hạn
1 ≤ k ≤ n ≤ 10^5; 1 ≤ ai ≤ 10^4.
Ví dụ 1 – vào
4 2 10 20 30 40
Ví dụ 1 – ra
60
Ví dụ 2 – vào
5 2 7 2 5 10 8
Ví dụ 2 – ra
18