Có n phần thưởng xếp thành một hàng dài, đánh số từ 1 đến n. Tùy thuộc vào số điểm đã đạt được của cặp chơi, người dẫn chương trình sẽ nói một số k (1 ≤ k ≤ n/3). Một người chơi sẽ chọn cho mình k phần thưởng xếp liên tiếp nhau, người thứ hai cũng sẽ chọn cho mình k phần thưởng xếp liên tiếp nhau trong số còn lại. Hermione là nữ nên được ưu tiên chọn trước.

Trò chơi đã kết thúc. Bây giờ không cần phải đồng tâm hiệp lực. Hermione vẫn còn rất giận Harry về một câu nói vô tâm mà chắc bây giờ Harry cũng không nhớ là mình nói cái gì và khi nào. Hermione hiểu rất rõ giá trị mỗi phần thưởng đối với Harry, cụ thể là phần thưởng thứ i sẽ có giá trị a[i] và quyết định cách chọn của mình sao cho tổng giá trị phần thưởng mà Harry có thể đạt được càng nhỏ càng tốt. Về tổng giá trị phần thưởng của mình, Hermione không mảy may quan tâm!

Yêu cầu: Tính x là tổng nhỏ nhất giá trị phần thưởng mà Hermione có thể chọn để Harry không có cách chọn phần thưởng với tổng giá trị lớn hơn x.

Input:

• Dòng đầu tiên chứa hai số nguyên dương n và k (1 ≤ n ≤ 10^5; 1 ≤ k ≤ n/3)

• Dòng tiếp theo ghi n số nguyên dương a[1], a[2], …, a[n]. (1 ≤ a[i] ≤ 10^9)

Output:

Số x tìm được.

Sample Input

10 2
1 2 4 5 2 4 2 2 1 6

Sample Output

7

Giải thích:

Hermione chọn phần thưởng số 3, 4. Sau khi Hermione chọn thì Harry có cách chọn hai phần thưởng liên tiếp với Giá trị lớn nhất có thể chọn là 7