Quá trình phát triển công nghiệp hóa – hiện đại hóa khiến tốc độ đô thị hóa ngày càng nhanh, nhưng ở nhiều miền quê Việt Nam vẫn tồn tại và lưu giữ những nét yên bình, mộc mạc. Nơi ấy, cuộc sống con người chầm chậm trôi như thể “bỏ qua” sự hối hả nơi phồn hoa đô thị ngoài kia. Buổi trưa, giữa nắng hè oi ả, đám trẻ lại hò nhau “trốn” bố mẹ vui đùa dưới những bụi tre già: đá bóng, bắn bi, ô ăn quan, ..., những trò chơi dân gian quen thuộc được các bạn nhỏ tổ chức, tham gia.

Hôm nay An và Linh tổ chức trò chơi mới. Để các bạn khác hiểu và tham gia trò chơi, An và Linh làm mẫu để các bạn khác xem và sau đó tham gia.

Trò chơi gồm \(N\) thẻ đánh số từ \(1\) tới \(N\), thẻ thứ \(i\) có giá trị \(a_i\). Trò chơi này quy ước rằng trong hai người mỗi người được chọn đúng \(K\) thẻ có chỉ số liên tiếp trong dãy (\(K \le \frac{N}{2}\)) và không được cùng chọn bất cứ thẻ nào.

Hôm nay làm mẫu cho các bạn nên An sẽ chọn trước, Linh chọn sau. Vì tính hiếu thắng, An muốn chọn một dãy \(K\) thẻ liên tiếp sao cho tổng giá trị lớn nhất mà Linh có thể đạt được từ các thẻ còn lại là nhỏ nhất có thể.

Yêu cầu: Xuất ra màn hình tổng giá trị lớn nhất Linh có thể đạt được sau khi An đã chọn tối ưu.

Input

• Dòng 1: Chứa hai số nguyên \(N, K\) (\(3 \le N \le 10^5; 1 \le K \le \frac{N}{2}\)).
• Dòng 2: Chứa \(N\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6\)).

Output

• Xuất ra màn hình một số nguyên duy nhất là kết quả tìm được.

Example

9 3
3 4 3 5 6 2 4 3 2

9

10 2
1 2 3 4 5 6 7 8 9 10

13

Scoring

• Có \(30\%\) số test tương ứng \(30\%\) số điểm thỏa mãn \(3 \le N \le 50; a_i \le 10^5\).
• Có \(30\%\) số test tương ứng \(30\%\) số điểm thỏa mãn \(3 \le N \le 5000; a_i \le 10^5\).
• Có \(40\%\) số test còn lại tương ứng \(40\%\) số điểm không có ràng buộc gì thêm.