Một công ty Logistics 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ứ ~i~ có trọng lượng là ~A_i~.

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 \ge K~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ mỗi số cách nhau một ký tự trống.

Output

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

Sample Input 1

5 2
1 3 2 3 5

Sample Output 1

8

Drone 1 vận chuyển các thùng hàng có trọng lượng ~1, 3, 2~. Drone 2 vận chuyển các thùng hàng có trọng lượng ~3, 5~. Chi phí vận chuyển đơn hàng được tính bằng năng lượng vận hành của Drone 2 = ~3 + 5 = 8~.

Sample Input 2

5 3
1 1 2 3 4

Sample Output 2

4

Drone 1 vận chuyển các thùng hàng có trọng lượng ~1, 1, 2~. Drone 2 vận chuyển các thùng hàng có trọng lượng ~3~. Drone 3 vận chuyển các thùng hàng có trọng lượng ~4~. Chi phí vận chuyển đơn hàng được tính bằng năng lượng vận hành của Drone 1 = ~1 + 1 + 2 = 4~ hoặc Drone 3 = ~4~.

Subtasks

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