Mô tả và yêu cầu

Ở đầu ra của một dây chuyền sản xuất trong nhà máy ZXY có một máy xếp tự
động. Sau khi kết thúc việc gia công trên dây chuyền, các sản phẩm sẽ được xếp vào các
hộp có cùng dung lượng M. Sản phẩm rời khỏi dây chuyền được xếp vào hộp đang mở
(khi bắt đầu ca làm việc có một hộp rỗng được mở sẵn) nếu như dung lượng của hộp
còn đủ để chứa sản phẩm. Trong trường hợp ngược lại, máy sẽ tự động đóng nắp hộp
hiện tại, cho xuất xưởng rồi mở một hộp rỗng mới để xếp sản phẩm vào. Trong một ca
làm việc có n sản phẩm đánh số từ 1 đến n theo đúng thứ tự mà chúng rời khỏi dây
chuyền. Sản phẩm thứ i có trọng lượng là ai, i = 1, 2, …, n. Ban Giám đốc nhà máy qui
định rằng sản phẩm xuất xưởng của mỗi ca làm việc phải được xếp vào trong không quá
k hộp.
Yêu cầu: Hãy giúp người quản đốc của ca làm việc xác định giá trị M nhỏ nhất
sao cho số hộp mà máy tự động cần sử dụng để xếp dãy n sản phẩm xuất xưởng của ca
không vượt quá số k cho trước.
* Input: đọc vào từ file văn bản ZXY.INP gồm:
Dòng đầu tiên chứa hai số nguyên n và k, (1 ≤ k ≤ n ≤ 105);
Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ai (ai ≤ 30000), i =1, 2,
…, n. Các số trên một dòng cách nhau ít nhất một dấu cách.
* Output: ghi ra file ZXY.OUT một số nguyên duy nhất là dung lượng của hộp.
* Example:
ZXY.INP ZXY.OUT
9 4 5
1
1
1
3
2
2
1
3
1