Trò chơi

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}{3}$) 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 Linh nhận được các thẻ có tổng giá trị 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.

Đọc từ bàn phím như sau:

• Dòng 1: Chứa 2 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, \dots, a_n$; ($\forall i: 1 \le a_i \le 10^6$).

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

Lưu ý: Bộ test đảm bảo luôn tồn tại đáp án.

• 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.