Một công ty kinh doanh tiến hành đánh giá hiệu quả làm việc của nhân viên A (check point) dựa trên tình hình doanh thu và chi phí của họ theo thời gian trong 1 giai đoạn công tác. Một giai đoạn công tác bao gồm một chuỗi các ngày làm việc được đánh số 1, 2, ..., N. Ngày làm việc thứ i của nhân viên A được đặc trưng bởi 1 con số (doanh thu hoặc chi phí) ai trong đó ai>0 có nghĩa ngày đó nhân viên thu được lượng tiền là ai (doanh thu), ai < 0 có nghĩa nhân viên cần chi tiêu một khoản −ai (chi phí). Hiệu quả làm việc của nhân viên A được đo bằng tổng lợi nhuận (tổng doanh thu - tổng chi phí) lớn nhất thu được trong số các chuỗi gồm một số liên tiếp các ngày mà trong đó có không quá K ngày nhân viên phải chi tiêu.
Ví dụ: giai đoạn kinh doanh gồm 9 ngày, trong đó lượng thu, chi của nhân viên được mô tả bởi dãy gồm 9 số: 100, -1, -2, -3, 60, -4, -5, 50, -10. Việc thu chi được thể hiện trong Bảng 1
Ngày 1 2 3 4 5 6 7 8 9
Thu 100 60 50
Chi 1 2 3 4 5 10
Bảng 1: Tình hình thu và chi của nhân viên A
Yêu cầu: cho giá trị N, K và dãy a1, ..., aN. Hãy tính hiệu quả công việc của nhân viên A.
Dữ liệu vào
- Dòng thứ nhất chứa 2 số nguyên dương N và K (1 ≤ N ≤ 105 , 0 ≤ K ≤ 100)
- Dòng thứ 2 chứa N số nguyên a1, . . . , aN
Kết quả
Ghi ra một số nguyên là hiệu quả làm việc của nhân viên A
Input
9 2
100 -1 -2 -3 60 -4 -5 50 -10
Output
101
Giải thích Hiệu quả công việc là tổng lợi nhuận thu được trong giai đoạn 4 ngày: 5, 6, 7, 8 và bằng 60 - 4 - 5 + 50 = 101.
Nguồn: ĐPT 20172018