Vào \(1\) ngày đẹp zời cuối tháng \(8\), ledinhbaonam đang học bài để chuẩn bị lụm top \(1\) lớp thì ahihiahihi từ đâu chui đến rủ anh đi chơi, dù không quen nhưng vì người rủ là con gái nên anh liên chấp nhận.
Để chuyến đi thật suôn sẻ, ahihiahihi đưa ra danh sách gồm \(N\) địa điểm du lịch theo thứ tự từ \(1\) đến \(N\). Tại mỗi địa điểm \(i\), cả hai cần tiêu tốn \(A_i\) đơn vị thời gian để tham quan. Để chuyến đi không quá mệt mỏi, ledinhbaonam đề xuất chia hành trình thành tối đa \(K\) giai đoạn, mỗi giai đoạn gồm một dãy các địa điểm liên tiếp.
Cả hai muốn tìm một giá trị \(X\) nhỏ nhất sao cho tổng thời gian tham quan trong mỗi giai đoạn không vượt quá \(X\).
Bạn hãy giúp ledinhbaonam và ahihiahihi tính toán giá trị \(X\) đó nhé!

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5\), \(1 \le K \le N\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_i\) (\(1 \le A_i \le 10^9\)).

Output

• Một số nguyên duy nhất là giá trị nhỏ nhất của \(X\) thỏa mãn yêu cầu bài toán.

Example

5 3
1 2 3 4 5

6

Scoring

• Subtask 1 (\(55\%\) số điểm): \(1 \le N \le 100, 1 \le A_i \le 100\).
• Subtask 2 (\(45\%\) số điểm): Không có ràng buộc nào thêm.