Harry và Hermione có ~n~ phần thưởng xếp thành một hàng, đánh số từ ~1~ đến ~n~. Người dẫn chương trình công bố một số ~k~ với ~1 \le k \le \lfloor n/3 \rfloor~.

• Hermione chọn trước một đoạn liên tiếp gồm đúng ~k~ phần thưởng.
• Sau đó Harry chọn tiếp một đoạn liên tiếp gồm đúng ~k~ phần thưởng không giao nhau với đoạn Hermione đã chọn (chọn trong các phần thưởng còn lại).

Hermione biết giá trị của từng phần thưởng đối với Harry: phần thưởng thứ ~i~ có giá trị ~a_i~. Hermione muốn chọn đoạn của mình sao cho tổng giá trị lớn nhất mà Harry có thể đạt được (nếu Harry chọn tối ưu) là nhỏ nhất có thể. Hermione không quan tâm tổng giá trị mình nhận được.

Yêu cầu

Tìm số nguyên ~x~ nhỏ nhất sao cho Hermione có thể chọn một đoạn dài ~k~ để đảm bảo: dù Harry chọn thế nào (hợp lệ), tổng giá trị đoạn của Harry không vượt quá ~x~.

Nói cách khác: ~ x=\min_{\text{đoạn } H \text{ dài } k}\ \ \max_{\text{đoạn } R \text{ dài } k,\ R \cap H = \varnothing}\ \sum_{i \in R} a_i ~ trong đó ~H~ là đoạn Hermione chọn, ~R~ là đoạn Harry chọn.

Dữ liệu

• Dòng 1: hai số nguyên ~n~ và ~k~.
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Kết quả

In ra một số nguyên ~x~ — giá trị lớn nhất mà Harry bị giới hạn sau khi Hermione chọn tối ưu.

Ví dụ

Ví dụ 1

Input

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

Output

7

Giải thích

Ví dụ 1

Các đoạn dài ~k=2~ có tổng lần lượt là:

• ~[1,2]: 1+2=3~
• ~[2,3]: 2+4=6~
• ~[3,4]: 4+5=9~ (lớn nhất)
• ~[4,5]: 5+2=7~
• ~[5,6]: 2+4=6~
• ~[6,7]: 4+2=6~
• ~[7,8]: 2+2=4~
• ~[8,9]: 2+1=3~
• ~[9,10]: 1+6=7~

Nếu Hermione chọn đoạn ~[3,4]~ (chặn đoạn có tổng ~9~), thì các đoạn Harry có thể chọn không giao nhau với ~[3,4]~ sẽ có tổng lớn nhất chỉ còn là ~7~ (ví dụ ~[4,5]~ không hợp lệ vì giao nhau, nhưng ~[9,10]~ hợp lệ và có tổng ~7~). Hermione không thể ép giá trị lớn nhất của Harry xuống dưới ~7~, nên đáp án là ~7~.

Ràng buộc và chấm điểm

Ràng buộc

• ~3 \le n \le 10^5~
• ~1 \le k \le \lfloor n/3 \rfloor~
• ~1 \le a_i \le 10^9~