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 \le 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~.

Input

• Dòng 1: Chứa 2 số nguyên ~n, k~ (~3 \le n \le 10^6; 1 \le k \le n/3~).
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~).

Output

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