Trước khi bước vào ngưỡng cửa đại học, hungnt quyết định lên kế hoạch đi du lịch trong đợt nghỉ hè tại quần đảo VNOI. Trong kì nghỉ này, anh ấy sẽ di chuyển từ hòn đảo này sang hòn đảo khác và tham quan các địa điểm du lịch tại mỗi hòn đảo để tích lũy kiến thức.

Ở quần đảo VNOI có ~n~ hòn đảo, các hòn đảo được đánh số từ ~0~ đến ~n - 1~. Có những cây cầu bắc qua các hòn đảo. Đối với hòn đảo ~i~ (~0 \le i \le n - 1~), có duy nhất một cây cầu nối đảo ~i~ với ~i-1~ và một cây cầu nối đảo ~i~ và ~i + 1~. Đảo ~0~ có một cây cầu nối với đảo ~1~, đảo ~n - 1~ có một cây cầu nối với đảo ~n - 2~.

Mỗi hòn đảo có một số địa điểm tham quan nhất định. hungnt dự kiến đi du lịch ~d~ ngày và muốn tham quan được nhiều địa điểm nhất. Anh ấy đã chọn một hòn đảo làm điểm xuất phát:

• Mỗi ngày anh ấy có thể di chuyển đến một hòn đảo liền kề hoặc tham quan tất cả các địa điểm du lịch của hòn đảo mà anh ấy đang ở, nhưng không thể làm cả hai việc trong cùng một ngày.

• hungnt không bao giờ tham quan một hòn đảo hai lần ngay cả khi anh ấy quay lại thành phố đó sau khi đã rời đi.

Bạn hãy giúp hungnt lên kế hoạch cho chuyến đi để tối đa hóa số lượng địa điểm tham quan mà anh ấy có thể ghé thăm trong khoảng thời gian ~d~ ngày.

Input

• Dòng đầu tiên gồm ba số nguyên ~n, st, d~ (~2 \le n \le 100000, 0 \le st \le n-1, 0 \leq d \leq 2n + \left\lfloor \frac{n}{2} \right\rfloor~) — số lượng hòn đảo, hòn đảo mà hungnt chọn làm điểm xuất phát và số ngày hungnt dự kiến đi du lịch.

• Dòng thứ hai gồm ~n~ số nguyên không âm ~a_0, a_1, a_2, \ldots a_{n - 1}~ (~0 \le a_i \le 10^9~) — lần lượt là số lượng địa điểm của các hòn đảo từ ~0~ đến ~n - 1~.

Output

• Một số nguyên duy nhất là số lượng địa điểm nhiều nhất mà hungnt có thể thăm quan trong ~d~ ngày.

Scoring

Sample Input 1

5 2 7
10 2 20 30 1

Sample Output 1

60

Notes

• Ngày 1, hungnt thăm các địa điểm ở đảo ~2~

• Ngày 2, di chuyển từ đảo ~2~ sang đảo ~3~

• Ngày 3, thăm các địa điểm ở đảo ~3~

• Ngày 4, di chuyển từ đảo ~3~ sang đảo ~2~

• Ngày 5, di chuyển từ đảo ~2~ sang đảo ~1~

• Ngày 6, di chuyển từ đảo ~1~ sang đảo ~0~

• Ngày 7, thăm các địa điểm ở đảo ~0~

• Tổng số lượng địa điểm hungnt đã thăm quan là: ~20 + 30 + 10 = 60~.