Giải bài trực tuyến

Sau một năm dài cố gắng, cuối cùng ĐB cũng đã cưa đổ TN. Nhưng TN là một cô gái nhìn xa thông rộng, nên đã tiên liệu trước được chuyện hai người chia tay và ĐB sẽ đòi quà. Tuy ĐB đã khẳng định không đòi lại quà, nhưng TN cứ khăng khăng nói phải tính chuyện này cho rõ ràng. ĐB nói TN cứ tự quyết định việc đó, nên TN đã đưa ra điều kiện như sau:

Giả sử ĐB tặng TN n món quà, mỗi món có giá trị a[i] (i = 1..n). TN sẽ lấy máy tính chọn một số k ngẫu nhiên (1 ≤ k ≤ n). Vậy trong n món quà, ĐB không được đòi lại k món liên tiếp.

Hãy giúp TN tính xem ĐB có thể đòi lại quà với tổng giá trị lớn nhất là bao nhiêu

Input : 

Dòng 1 : gồm 2 số n và k

Dòng 2 : gồm n số, số thứ i là a[i] (i = 1..n), các số cách nhau ít nhất một khoảng trắng

Output : 

Một số duy nhất là tổng giá trị quà lớn nhất mà ĐB có thể đòi được 

Giới hạn : 

 - 0 ≤ a[i] ≤ 10⁶

 - n ≤ 10⁶

Ví dụ : 

Input:

5 3

6 19 8 7 13

Output:

45

Bonus :