Trứng vào thùng

Có \(N\) quả trứng chạy trên băng chuyền theo thứ tự, quả thứ \(i\) có thể tích \(a_i\). Ở cuối băng chuyền có \(M\) thùng đặt liên tiếp, mỗi thùng có sức chứa \(K\) như nhau. Các quả trứng lần lượt được cho vào thùng đầu tiên cho đến khi quả kế tiếp không còn vừa (tổng thể tích sẽ vượt \(K\)), khi đó chuyển sang thùng tiếp theo và cứ thế tiếp tục.

Hãy tìm \(K\) nhỏ nhất (số nguyên không âm) sao cho \(M\) thùng chứa hết tất cả trứng.

Input

• Dòng đầu gồm hai số nguyên \(N, M\).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra giá trị \(K\) nhỏ nhất.

Constraints

• \(1 \le N \le 10^6\)
• \(1 \le M \le 10^9\)
• \(0 \le a_i \le 10^6\)

Sample Input

6 3
3 7 2 5 4 6

Sample Output

10

Explanation

Với \(K = 10\): thùng 1 chứa \(3+7\), thùng 2 chứa \(2+5\), thùng 3 chứa \(4+6\). Với \(K = 9\) thì phải dùng ít nhất \(4\) thùng.