#874. MEMORIES - Hồi ký

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Để chuẩn bị cho ngày kỷ niệm 20 năm thành lập trường, Đoàn Trường phát động một phong trào viết hồi ký về những năm tháng tuổi học trò. Phong trào nhận được sự hưởng ứng nhiệt liệt của các bạn học sinh cũng như cựu học sinh, của các thầy cô đang và đã giảng dạy ở trường. Các bài viết đều rất chất lượng, khó có thể loại bỏ. Người ta quyết định phân loại các bài viết thành các chương.

Kết quả biên tập là một cuốn kỷ yếu gồm n chương, chương thứ i a_i trang, i=1÷n , nếu in thành một cuốn sách thì quá dày, vì vậy người ta quyết định in không quá k tập, mỗi chương phải nằm gọn trong một tập, tập 1 bao gồm một số chương đầu tiên, mỗi tập tiếp theo bao gồm một số chương tiếp, theo đúng trình tự như in tất cả các chương liên tiếp thành một cuốn.

Ban biên tập phải có nhiệm vụ phân chia sao cho số trang của tập dày nhất là ít nhất.

Ví dụ, với n=5 , số trang trong mỗi chương tương ứng lần lượt là 3, 7, 12, 8, 5 và dự kiến in thành 3 tập thì tập 1 sẽ chứa chương 1 2 với tổng số trang là 10 , tập 2 chứa chương 3 với tổng số trang là 12 , tập 3 chứa hai chương cuối với tổng số trang là 13 . Như vậy, tập dày nhất có số trang là 13 và đây cũng là cách phân chia phù hợp với yêu cầu đã nêu.

Hãy xác định số trang của tập dày nhất nhận được sau kết quả làm việc của ban biên tập.

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên n k\ (1≤k≤n≤10^5) ;
  • Dòng thứ hai chứa n số nguyên a_1,a_2, \ldots,a_n\ (1≤a_i≤10^9,i=1÷n) .

Kết quả:

Đưa ra một số nguyên – số trang của tập dày nhất.

Ví dụ:

Dữ liệu:

5 3
3 7 12 8 5

Kết quả:

13

Ràng buộc:

  • 20\% số test tưng ứng 20\% số điểm có a_i≤100;n≤20 ;
  • 30\% số test khác tương ứng 30\% số điểm có n≤10^2 ;
  • 50\% số test còn lại tương ứng 50\% số điểm có n≤10^5 .