Mô tả bài toán

Bạn được cung cấp ~ n ~ gói hàng có trọng lượng ~ w_i ~ và cần chuyển chúng bằng ~ k ~ xe tải, mỗi xe có tải trọng tối đa ~ P ~. Mỗi xe tải có thể chở các kiện hàng liên tiếp, miễn là tổng trọng lượng của các kiện không vượt quá ~ P ~.

Yêu cầu: Tìm giá trị tối thiểu của tải trọng tối đa ~ P ~ để tất cả ~ n ~ gói hàng được chuyển.

Input:

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ k ~ (~ 1 \leq n, k \leq 100,000 ~).
• Dòng tiếp theo chứa ~ n ~ số nguyên ~ w_1, w_2, \ldots, w_n ~ (~ 1 \leq w_i \leq 10,000 ~) là trọng lượng của các gói hàng.

Output:

• In một số nguyên duy nhất là giá trị nhỏ nhất của ~ P ~.

Ví dụ:

Input:

5 3
8 1 7 3 9

Output:

10

Giải thích:

• Xe thứ nhất chở ~ \{8, 1\} ~ (tổng ~ 9 ~).
• Xe thứ hai chở ~ \{7, 3\} ~ (tổng ~ 10 ~).
• Xe thứ ba chở ~ \{9\} ~.
• Giá trị ~ P = 10 ~ là nhỏ nhất thoả mãn.