Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_n~ và một số nguyên ~k~.

Người thứ nhất chọn trước một đoạn liên tiếp gồm đúng ~k~ phần tử. Sau đó, người thứ hai chọn một đoạn liên tiếp gồm đúng ~k~ phần tử trong số các phần tử còn lại.

Giá trị người thứ hai nhận được bằng tổng các phần tử trong đoạn mà mình chọn. Người thứ nhất chọn sao cho giá trị lớn nhất mà người thứ hai có thể đạt được là nhỏ nhất.

Yêu cầu

Hãy xác định giá trị nhỏ nhất ~x~ sao cho người thứ nhất có thể chọn trước để sau đó người thứ hai không thể thu được tổng lớn hơn ~x~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Kết quả

In ra một số nguyên ~x~.

Ví dụ

Ví dụ 1

Input

10 2
1 2 4 5 2 4 2 2 1 6

Output

7

Giải thích

Ví dụ 1

Nếu người thứ nhất chọn đoạn ~[3, 4]~ hoặc ~[4, 5]~, thì tổng lớn nhất mà người thứ hai có thể nhận được trong phần còn lại là ~7~.

Do đó đáp án là ~7~.

Ràng buộc và chấm điểm

Ràng buộc

• ~3 \le n \le 10^5~
• ~1 \le k \le n/3~
• ~1 \le a_i \le 10^9~