Bước nhẩy Kangaroo


Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

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é. 1

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

tichpx

Comments

There are no comments at the moment.