Vào dịp Tết Nguyên Đán, thành phố tổ chức một "Con Đường Hoa" trải dài để người dân du xuân, thưởng ngoạn. Con đường này được chia thành khu vực trang trí liên tiếp, được đánh số từ đến .
Mỗi khu vực có một điểm ấn tượng là . Giá trị có thể là số dương (trải nghiệm tích cực) hoặc số âm (trải nghiệm tiêu cực).
Một du khách khi đến tham quan sẽ chọn đi bộ qua một đoạn đường liên tiếp các khu vực (từ khu vực đến khu vực ). Để đảm bảo sức khỏe và trải nghiệm trọn vẹn, chuyến đi bộ này phải tuân thủ quy tắc về độ dài:
Ban tổ chức muốn đánh giá tiềm năng của từng khu vực để rút kinh nghiệm cho năm sau. Với mỗi khu vực (từ đến ), họ đặt câu hỏi: "Tổng điểm ấn tượng lớn nhất của một du khách đi qua điểm có thể nhận được là bao nhiêu?"
Hãy giúp Ban tổ chức tính toán giá trị này cho tất cả các khu vực.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên , lần lượt là số lượng khu vực trên đường hoa và giới hạn độ dài tối thiểu, tối đa của hành trình;
Dòng thứ hai chứa số nguyên (, là điểm ấn tượng của từng khu vực.
Kết quả:
In ra một dòng duy nhất chứa số nguyên, số thứ là tổng điểm ấn tượng lớn nhất của hành trình đi qua khu vực thỏa mãn điều kiện độ dài.
Ví dụ:
Dữ liệu:
5 1 3
-1 -6 7 7 -4
Kết quả:
0 8 14 14 10
Giải thích: Các hành trình tối ưu đi qua mỗi điểm tương ứng là: , , , , .
Giới hạn:
Subtask #1: số điểm có ;
Subtask #2: số điểm khác có ;
Subtask #3: số điểm khác có ;
Subtask #4: số điểm khác có ;
Subtask #5: số điểm còn lại không có ràng buộc bổ sung.
