Phát quà (phatqua2.*)

Lập trình ngày nay đang là một môn học yêu thích của giới trẻ. Nam là tình nguyện viên dạy lập trình cho các em tại trung tâm ITCENTER, thấy các em học tập say mê và tràn đầy nhiệt huyết Nam quyết định tặng quà cho hai em học sinh chăm chỉ và có điểm số cao nhất lớp học hôm nay là Bình và An nhằm khuyến khích phong trào học tập trong lớp. Nam mang tới lớp học của Bình và An \(n\) gói quà đánh số từ 1 tới \(n\), gói quà thứ \(i\) có giá trị \(a_{i}\). Nam nói rằng trong hai em mỗi em được chọn đúng k món quà có chỉ số liên tiếp trong dãy \((k \leq \frac{n}{3})\) và không được cùng chọn bất cứ món quà nào.

Nghe vậy Bình xung phong chọn trước và An chọn sau. Vì bản tính hiếu thắng, Bình muốn An 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 Bình chọn quà mà An không thể có cách chọn được tổng giá trị quà lớn hơn \(x\).

Dữ liệu vào:

Dòng 1: Chứa 2 số nguyên \(n,k\ (3 \leq n \leq 10^{6};1 \leq k \leq \frac{n}{3})\).

Dòng 2 chưa \(n\) số nguyên \(a_{1},a_{2},...,a_{n};(\forall i:1 \leq a_{i} \leq 10^{6}).\).

Kết quả: Ghi một số nguyên duy nhất là giá trị 𝑥 tìm được.

Ví dụ:

Input	Output
10 2 1 2 4 5 2 4 2 2 1 6	7

Giải thích: Bình chọn món quà thứ 4 và thứ 5, khi đó An chỉ có thể chọn quà với tổng giá trị tối đa bằng 7 (Chọn món quà thứ 9 và thứ 10).

Ràng buộc:

Subtask 1: Có 30% số điểm thỏa mãn \(3 \leq n \leq 50;a_{i} \leq 10^{5}.\)

Subtask 2: Có 30% số điểm thỏa mãn \(3 \leq n \leq 5000;a_{i} \leq 10^{5}.\)

Subtask 3: Có 40% số điểm không có ràng buộc gì thêm.