Doanh thu

Doanh thu của một công ty trong $N$ ngày tiếp theo (các ngày được đánh số từ 1 đến $N$, $1 < N \le 10^5$) dự kiến lần lượt là $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^9$). Hội đồng quản trị của công ty muốn chọn ra ít nhất $K$ ngày liên tiếp nhau ($1 \le K < N$) sao cho tổng doanh thu trong những ngày được chọn là lớn nhất.

Yêu cầu: Tính tổng doanh thu lớn nhất mà hội đồng quản trị có thể chọn được.

Từ file văn bản CAU3.INP gồm:

• Dòng thứ nhất chứa hai số nguyên dương $N$ và $K$;
• Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, \dots, A_N$.

Ghi ra file văn bản CAU3.OUT một số duy nhất là tổng doanh thu lớn nhất chọn được.

• Có 40% số điểm: $1 < N \le 200$;
• Có 30% số điểm: $200 < N \le 2000$;
• Có 30% số điểm còn lại không có ràng buộc gì thêm.