Cirno (Cirno)

Nguồn: Luogu

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có các ô từ $0$ đến $N$. Từ ô $i$ chỉ được nhảy tới một ô trong $[i+L,i+R]$. Khi dừng ở ô $i$ nhận giá trị $A_i$. Bắt đầu ở ô $0$ với $A_0=0$; khi bước tiếp theo vượt quá $N$ thì đã sang bờ. Tìm tổng giá trị lớn nhất.

Input

Dòng đầu chứa $N,L,R$. Dòng thứ hai chứa $N+1$ số $A_0,\ldots,A_N$.

Output

In giá trị lớn nhất đạt được khi sang bờ.

Subtask

• Subtask 1 (60%): $N \le 10^4$.
• Subtask 2 (40%): $N \le 2\cdot 10^5$.

Toàn bộ dữ liệu tuân theo: $N \le 2\cdot10^5$, $-10^3 \le A_i \le 10^3$, $1 \le L \le R \le N$; đáp án không vượt $2^{31}-1$.

Ví dụ

Input

5 2 3
0 12 3 11 7 -2

Output

11

Giải thích

Theo quy tắc nhảy $2$ đến $3$ ô, một lộ trình tối ưu cho tổng chỉ số đóng băng bằng $11$ trước khi bước vượt bờ.