Bài 5. Trò chơi (5,0 điểm; Đề HSG9 tỉnh Đắk Lắk 2025-2026)

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

Dữ liệu vào:

• Dòng 1: Chứa 2 số nguyên N, K (3 ≤ N ≤ 10⁶; 1 ≤ K ≤ N / 3).
• Dòng 2 chứa N số nguyên a₁, a₂, ..., a_n (với 1 ≤ a_i ≤ 10⁶).

Dữ liệu ra: 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.

Ví dụ:

Giải thích:

• Ví dụ 1: An chọn các thẻ thứ 3, 4, 5, khi đó Linh chỉ có thể chọn các thẻ với tổng giá trị tối đa bằng 9 (chọn các thẻ thứ 6, 7, 8 hoặc 7, 8, 9).
• Ví dụ 2: An chọn các thẻ thứ 8 và thứ 9, khi đó Linh chỉ có thể chọn các thẻ với tổng giá trị tối đa bằng 13 (chọn các thẻ thứ 6 và thứ 7).

Giới hạn:

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