Có ~N~ quả dưa hấu trên một băng chuyền, quả thứ ~i~ có thể tích là ~A_i~. Băng chuyền lần lượt đẩy các quả dưa từ quả thứ ~1~ đến quả thứ ~N~ xuống các thùng.

Ngay dưới băng chuyền có ~K~ thùng cùng sức chứa ~X~. Nếu thùng hiện tại không thể chứa thêm quả dưa sắp được đẩy xuống thì băng chuyền tự động chuyển sang thùng tiếp theo.

Hãy tìm sức chứa ~X~ nhỏ nhất sao cho ~K~ thùng có thể chứa được tất cả ~N~ quả dưa hấu.

Input

• Dòng đầu tiên gồm hai số nguyên ~N, K~ ~(N, K \le 10^5)~;

• Dòng tiếp theo gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(A_i \le 10^9)~.

Output

In ra giá trị ~X~ nhỏ nhất sao cho có thể chứa tất cả ~N~ quả dưa trong ~K~ thùng.

Scoring

Sample Input 1

6 3
3 5 3 6 1 8

Sample Output 1

9

Notes

Thùng thứ nhất chứa các quả ~1, 2~; thùng thứ hai chứa các quả ~3, 4~; thùng thứ ba chứa các quả ~5, 6~.