Farmer John là bậc thầy kế toán đáng kinh ngạc và nhận ra có thể hết tiền vận hành trại. Ông đã tính và ghi chính xác chi phí ($1 \le money_{i} \le 10,000$) mỗi ngày trong $N$ ngày tới ($1 \le N \le 100,000$).
FJ muốn ngân sách cho đúng $M$ kỳ tài chính nối tiếp ($1 \le M \le N$), tên «fajomonths». Mỗi kỳ có một hoặc nhiều ngày liên tiếp, mỗi ngày thuộc đúng một kỳ.
Ông muốn chia kỳ để tối thiểu hóa chi phí của kỳ tốn nhiều nhất, qua đó định hạn mức tháng.
Dữ liệu vào
Dòng 1: hai số nguyên cách nhau bởi dấu cách: $N$ và $M$. Dòng $2\ldots N+1$: dòng $i+1$ chứa số đô la Farmer John chi ngày $i$.
Dữ liệu ra
Dòng 1: hạn mức tháng nhỏ nhất có thể mà Farmer John chấp nhận.
Ví dụ
Dữ liệu vào 1
7 5 100 400 300 100 500 101 400
Dữ liệu ra 1
500
Ghi chú
Nếu hai ngày đầu thành một tháng, ngày ba và bốn một tháng, ba ngày cuối mỗi ngày một tháng riêng, không tháng nào quá 500 đô la. Mọi cách chia khác cần hạn mức tháng tối thiểu lớn hơn.
Nguồn bài: USACO, tháng 3 năm 2007.