Trường học của chúng ta vừa xây xong một dãy gồm N bức tường xếp thành một hàng ngang. Bức tường thứ i có diện tích là A_i. Để chuẩn bị cho năm học mới, nhà trường đã thuê một đội thợ sơn gồm K người để sơn lại toàn bộ dãy tường này.

Quy định

• Mỗi người thợ sơn sẽ được giao sơn một số bức tường nằm liên tiếp nhau (không được nhảy cóc).
• Một người thợ có thể không phải sơn bức tường nào (nếu số lượng thợ nhiều hơn số bức tường).
• Thời gian để một người thợ hoàn thành công việc của mình đúng bằng tổng diện tích các bức tường mà người đó được giao sơn.
• Tất cả các thợ sơn đều bắt đầu làm việc cùng một lúc.
• Thời gian để hoàn thành toàn bộ công trình sẽ được tính bằng thời gian của người thợ sơn làm việc lâu nhất.

Ban quản lý muốn tìm ra một cách phân công công việc sao cho thời gian hoàn thành công trình là nhỏ nhất có thể.

Yêu cầu

Hãy tính thời gian ngắn nhất để hoàn thành việc sơn toàn bộ N bức tường.

Dữ liệu vào (Input)

Dòng thứ nhất chứa hai số nguyên dương N và K (1 <= N <= 10^5, 1 <= K <= 10^4), cách nhau một khoảng trắng.
Dòng thứ hai chứa N số nguyên dương A_1, A_2, ..., A_N (1 <= A_i <= 10^9), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra (Output)

Ghi ra một số nguyên duy nhất: Thời gian ngắn nhất để hoàn thành công trình.

Ràng buộc

Subtask 1 (30% số điểm): 1 <= N <= 20; 1 <= K <= 5; 1 <= A_i <= 100.
Subtask 2 (30% số điểm): 1 <= N <= 1000; 1 <= K <= 100; 1 <= A_i <= 10^5.
Subtask 3 (40% số điểm): 1 <= N <= 10^5; 1 <= K <= 10^4; 1 <= A_i <= 10^9.

Ví dụ

Input:
4 2
10 20 30 40

Output:
60

(Giải thích: Thợ 1 sơn tường 1, 2, 3 tổng là 60. Thợ 2 sơn tường 4 tổng là 40. Thời gian là max(60, 40) = 60).