Lại nói về câu truyện Cây khế năm ấy, sau khi ăn một quả khế, Đại bàng nói với cậu chủ “Ăn một quả trả một cục vàng, may túi ba gang mang đi mà đựng”. Đại bàng hứa sẽ chở cậu chủ \(k\) chuyến đến hòn đảo nhỏ xa xôi, trên hòn đảo có \(n\) đồ vật được đánh số từ 1 đến \(n\) từ ngoài cửa hang vào trong, đồ vật thứ \(i\) có khối lượng \(a_{i}\).Cậu chủ phải lấy lần lượt các đồ vật từ ngoài vào trong. Công việc của cậu chủ là phải may một chiếc túi đựng được tổng khối lượng \(m\) càng nhỏ càng tốt sao cho sau \(k\) chuyến có thể lấy được hết \(n\) đồ vật trên đảo.

Yêu cầu: Hãy tìm giá trị \(m\) nhỏ nhất .

Dữ liệu vào:

+ Dòng thứ nhất: Hai số nguyên dương \(n,k\) , giữa hai số cách nhau một khoảng trắng \((1 \leq n \leq 10^{5};k \leq n).\)

+ Dòng thứ hai: \(n\) số nguyên dương \(a_{1},a_{2},...,a_{N}(a_{i} \leq 10^{9}\)với \(1 \leq i \leq n)\), các số cách nhau một khoảng trắng.

Kết quả:

+ Ghi một số nguyên duy nhất là giá trị \(m\) nhỏ nhất tìm được

Ví dụ:

Ràng buộc:

+ Có 60% số test tương ứng với 60% số điểm của bài thỏa mãn \(n \leq 5000;a_{i} \leq 1000;\)

+ Có 40% số test tương ứng với 40% số điểm của bài không có thêm ràng buộc gì.