Trong chương trình "Tủ sách học đường cho em", Sở Giáo dục và Đào tạo tỉnh Sơn La chuyển giao ~n~ cuốn sách cho một trường phổ thông dân tộc bán trú xã vùng biên. Cuốn sách thứ ~i~ có độ dày ~a_i~ trang. Toàn bộ những cuốn sách này sẽ được giữ nguyên thứ tự và chia thành ~K~ nhóm gồm các cuốn sách liên tiếp để giao cho ~K~ nhóm học sinh cùng đọc.

Với một cách chia cụ thể, ta gọi ~t_1, t_2, \dots, t_K~ là tổng số trang của những cuốn sách trong mỗi nhóm, đặt ~t_{max} = \max\limits_{1 \le j \le K} t_j~. Nhà trường mong muốn tìm cách chia tối ưu với ~t_{max}~ đạt giá trị nhỏ nhất. Hãy giúp nhà trường tính toán giá trị ~t_{max}~ trong cách chia tối ưu đó.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~K~ ~(1 \le K \le n \le 10^5)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

• Một số nguyên là giá trị ~t_{max}~ của cách chia tối ưu.

Scoring

Sample Input 1

4 2
12 34 67 90

Sample Output 1

113

Notes

• Có ~3~ cách chia, cách tối ưu là ~[12, 34, 67]~, ~[90]~ với tổng số trang tương ứng là ~113~ và ~90~.