Jian-Jia đang lên kế hoạch cho kỳ nghỉ tiếp theo tại Đài Loan. Trong kỳ nghỉ, cậu di chuyển giữa các thành phố và tham quan các điểm du lịch trong những thành phố đó.

Có \(n\) thành phố, tất cả nằm dọc theo một con đường cao tốc, được đánh số liên tiếp từ \(0\) đến \(n-1\). Với thành phố \(i\) thỏa mãn \(0<i<n-1\), hai thành phố liền kề là \(i-1\) và \(i+1\). Thành phố duy nhất liền kề với thành phố 0 là thành phố 1; thành phố duy nhất liền kề với thành phố \(n-1\) là thành phố \(n-2\).

Mỗi thành phố có một số điểm du lịch. Jian-Jia có \(d\) ngày nghỉ và muốn tham quan nhiều điểm du lịch nhất có thể. Cậu đã chọn sẵn thành phố xuất phát. Trong mỗi ngày, Jian-Jia hoặc di chuyển đến một thành phố liền kề, hoặc tham quan tất cả các điểm du lịch của thành phố đang ở, nhưng không thể làm cả hai. Jian-Jia không bao giờ tham quan các điểm du lịch trong cùng một thành phố hai lần, ngay cả khi cậu đến thành phố đó nhiều lần. Hãy giúp cậu lập kế hoạch để tham quan được nhiều điểm du lịch khác nhau nhất.

Ví dụ

Giả sử Jian-Jia có 7 ngày nghỉ, có 5 thành phố với số điểm du lịch như bảng dưới đây, và cậu xuất phát từ thành phố 2.

Thành phố  Số điểm du lịch
0          10
1          2
2          20
3          30
4          1

Ngày thứ nhất, Jian-Jia tham quan 20 điểm du lịch ở thành phố 2. Ngày thứ hai, cậu di chuyển từ thành phố 2 đến thành phố 3. Ngày thứ ba, cậu tham quan 30 điểm du lịch ở thành phố 3. Cậu dùng ba ngày tiếp theo để đi từ thành phố 3 đến thành phố 0, rồi tham quan 10 điểm du lịch ở thành phố 0 vào ngày thứ bảy.

Ngày  Hoạt động
1     Tham quan các điểm du lịch ở thành phố 2
2     Di chuyển từ thành phố 2 đến thành phố 3
3     Tham quan các điểm du lịch ở thành phố 3
4     Di chuyển từ thành phố 3 đến thành phố 2
5     Di chuyển từ thành phố 2 đến thành phố 1
6     Di chuyển từ thành phố 1 đến thành phố 0
7     Tham quan các điểm du lịch ở thành phố 0

Tổng số điểm du lịch được tham quan là

Đây là số điểm du lịch lớn nhất có thể tham quan trong 7 ngày nếu xuất phát từ thành phố 2.

Nhiệm vụ

Hãy cài đặt hàm findMaxAttraction(n, start, d, attraction) để tính số điểm du lịch lớn nhất Jian-Jia có thể tham quan.

• n: số thành phố.
• start: chỉ số thành phố xuất phát.
• d: số ngày nghỉ.
• attraction: mảng độ dài \(n\); attraction[i] là số điểm du lịch ở thành phố \(i\), với \(0 \le i \le n-1\).
• Hàm phải trả về số điểm du lịch lớn nhất Jian-Jia có thể tham quan.

Các subtasks

Trong tất cả các subtasks, số điểm du lịch ở mỗi thành phố là không âm và

Các ràng buộc bổ sung:

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên holiday.c, holiday.cpp hoặc holiday.pas, cài đặt chương trình con theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề holiday.h.

Lưu ý: kết quả có thể rất lớn; kiểu trả về của findMaxAttraction là số nguyên 64 bit.

C/C++:

long long int findMaxAttraction(int n, int start, int d,
int attraction[]);

Pascal:

function findMaxAttraction(n, start, d : longint;
attraction : array of longint): int64;

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: n, start, d.
• Dòng 2: attraction[0], ..., attraction[n-1].

Trình chấm mẫu in giá trị trả về của findMaxAttraction.