Mã bài:
divmooncake
Điểm:
2,8 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Tèo đang vui chơi trong không khí sôi nổi của mùa Trung thu ở công viên. Ở đó, Tèo thấy rất nhiều các gian hàng bánh trung thu rất bắt mắt nên liền chạy lại xem. Những chiếc bánh trung thu được trưng bày rất hấp dẫn làm cho Tèo chảy hết cả nước bọt. Ban đầu, Tèo chỉ tính mua cho bản thân mình nhưng khi biết được chương trình khuyến mãi Tèo đã đổi ý muốn mua về cho cả xóm.
Cụ thể, các em nhỏ nào thông minh chọn ra được tổng số lượng bánh trung thu lớn nhất nhưng không được chọn quá ~K~ quầy liên tiếp thì sẽ được miễn phí toàn bộ số bánh đó. Vì muốn làm người tốt nên Tèo quyết định cố gắng làm bài tập này. Thật may mắn cậu có đem laptop để thuận tiện việc tính toán, mỗi tội cậu không biết lập trình. Là một lập trình viên, hãy giúp Tèo nhé.
Dữ liệu vào
- Dòng thứ nhất gồm hai số nguyên dương ~N,K\,(K \le N \le 10^5)~ với ~N~ là số gian hàng.
- Dòng tiếp theo gồm các số ~a_1,a_2,\dots,a_N~ ~(a_i \le 10^9)~ là số lượng bánh mỗi gian hàng.
Kết quả ra
- Một dòng là kết quả bài toán
Ràng buộc
- Có ~80\%~ số test tương ứng với ~80\%~ số điểm có ~N \cdot K \le 10^6~.
- ~20\%~ test còn lại không ràng buộc gì thêm
-
Ví dụ 1
Dữ liệu
5 3
5 3 12 4 25
Kết quả
46
Chú thích
- Chọn các quầy có số bánh trung thu: ~5 + 12 + 4 + 25 = 46~.
Bình luận