Một công ty Logicstics có \(K\) Drone giao hàng. Công ty nhận một đơn hàng vận chuyển \(N\) thùng hàng, các thùng hàng được đánh số thứ tự từ \(1\) đến \(N\), thùng hàng thứ \(l\) có trọng lượng là \(A_l\).

Mỗi Drone tham gia sẽ vận chuyển các thùng hàng liên tiếp trong đơn hàng mà không làm thay đổi thứ tự các thùng hàng. Năng lượng vận hành của mỗi Drone được tính bằng tổng trọng lượng của các thùng hàng trên Drone. Chi phí của đơn hàng được tính bằng năng lượng vận hành lớn nhất trong các Drone tham gia vận chuyển.

Yêu cầu: Tính chi phí thấp nhất để vận chuyển đơn hàng.

Input

• Dòng thứ nhất chứa số nguyên dương \(N\) và \(K\) mỗi số cách nhau một ký tự trống (\(N \geq K\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) mỗi số cách nhau một ký tự trống.

Output

• Ghi ra một số nguyên duy nhất là chi phí thấp nhất để vận chuyển đơn hàng.

Example

5 2
1 3 2 3 5

8

5 3
1 1 2 3 4

4

Scoring

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