Hè sắp đến, trung tâm Anh ngữ ABC Smart lại tổ chức cho các bạn học viên đi tham quan. Năm nay các học viên được tham quan trên một khu vườn trồng cam ở Huyện Thọ Xuân. Các em rất ấn tượng trước một vườn cam gồm \(N\) cây được trồng thành một hàng thẳng tắp, cách đều nhau (khoảng cách từ gốc cây \(i\) đến gốc cây \(i + 1\) bằng \(K\) (với mọi \(i = 1. . N − 1\)). Năm nay được mùa cam nên cây nào cũng sai quả, cây thứ \(i\) có \(A_i\) quả cam. Giám đốc trung tâm quyết định chọn ra 1 học viên may mắn và thưởng cho học viên này theo quy tắc sau:

“Học viên có thể đứng tại một vị trí bất kỳ. Phần thưởng là tất cả số quả cam thuộc các cây có khoảng cách đến vị trí học viên đang đứng không lớn hơn khoảng cách H cho trước”.

Yêu cầu:

Hãy cho biết số lượng quả cam lớn nhất mà học viên có thể nhận được bằng bao nhiêu?

Dữ liệu:

Vào từ file CAMTX.INP gồm:

• Dòng 1: chứa 3 số nguyên dương \(N,K, H\) \((1 \le N \le 10^6, 1 \le K, H \le 10^9)\).

• Dòng 2: chứa \(N\) số nguyên \(A_1, A_2,..., A_N\). Trong đó \(A_i\) là số lượng quả cam của cây cam thứ \(i\); \(0 \le A_i \le 10^9\) với \(1 \le i \le N\).

Kết quả:

Ghi ra file CAMTX.OUT gồm một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Giải thích:

Trong ví dụ trên, học viên đứng ở chính giữa cây cam thứ 4 và thứ 5 thì sẽ nhận được tổng số quả cam cần tìm bằng: 4+5+1+6 = 16.

Giới hạn:

• Có \(20\%\) số điểm có \(K=H\);

• Có \(20\%\) số điểm \(N \le 10^2\);

• Có \(20\%\) số điểm \(N \le 10^3\);

• Có \(40\%\) số điểm ứng với các điều kiện còn lại.