Nhân dịp đại diện của làng đăng quang hoa hậu vương quốc, nhà vua tổ chức phát quà cho tất cả các thiếu nữ trong làng nhằm khuyến khích phong trào làm đẹp. Sứ giả của nhà vua mang tới nhà của Tấm và Cám ~n~ gói quà đánh số từ 1 tới ~n~, gói quà thứ ~i~ có giá trị ~a_i~. Sứ giả nói rằng mỗi cô gái được chọn đúng ~k~ món quà có chỉ số liên tiếp trong dãy (~k \le \frac{n}{3}~) và không được cùng chọn bất cứ món quà nào.

Nghe vậy, bà dì ghẻ cho Cám chọn trước và bắt Tấm phải chọn sau. Vì bản tính đố kỵ, Cám muốn Tấm nhận được dãy quà có tổng giá trị nhỏ nhất có thể.

Yêu cầu: Tìm số ~x~ nhỏ nhất sao cho tồn tại phương án Cám chọn quà mà Tấm không thể có cách chọn được tổng giá trị quà lớn hơn ~x~.

Input

• Dòng 1 chứa hai số nguyên ~n, k~ (~3 \le n \le 10^6; 1 \le k \le\frac{n}{3}~)
• Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~; ~(1 \le a_i \le 10^6)~

Các số trên 1 dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là giá trị ~x~ tìm được.

Sample

Input #1

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

Output #1

7

Hint

• Cám chọn món quà thứ 4 và thứ 5, khi đó Tấm chỉ có thể chọn quà với tổng giá trị tối đa là 7 (món thứ 9 và thứ 10)

Problem source: PreVNOI Ⅶ (NINH BÌNH 2017)