Bước nhẩy Kangaroo
Dạo này tại xứ sở UTC mới đem về nuôi một con Kangaroo để nghiên cứu các điệu nhẩy bất hủ của nó. Con Kangaroo này mỗi bước nhẩy của nó khoảng cách ngắn nhất là X đơn vị độ dài, xa nhất là Y đơn vị độ dài. Người ta có treo các phần thưởng trên các cột thuộc một đường thắng các cột cách nhau đúng 1 đơn vị độ dài. Con Kangaroo có thể xuất phát từ bất kỳ cột nào và nó nhảy theo khả năng của nó đến lúc nào nó chán để thu được các phần thưởng trên các cột. Bạn hãy tư vấn giúp Kangaroo lấy được phần thưởng nhiều nhất là bao nhiêu nhé.
Input
Dòng đầu là 3 số nguyên dương n,X,Y tương ứng là số cột và khoảng nhẩy ngắn nhất và xa nhất của Kangaroo \((1< n \le 10^6)\) \( 1 \le X < Y \le 10^6\)
Dòng thứ 2 là \(n\) giá trị các phần thưởng tại lần lượt từng cột có giá trị tuyệt đối không vượt quá \(10^4\)
Output
Tổng giá trị phần thưởng lớn nhất có thể có của Kangaroo biết rằng nó phải nhận ít nhất 1 phần thưởng
Ví dụ 1
Input
10 2 3
-9 4 -7 -8 -2 1 5 3 -6 -2
Output
7
Giải thích Con Kangaroo đã nhảy tại các vị trí a[2]=4, a[5]=-2, a[7]=5 có tổng là 7
Ví dụ 2
Input
10 2 3
-9 -4 -7 -8 -2 -1 -5 -3 -6 -2
Output
-1
Giải thích Con Kangaroo đã nhảy tại 1 vị trí a[6]=-1
Comments