Bé An mới đi học mẫu giáo. Để bé yêu thích việc đến trường, cô giáo tổ chức một trò chơi thú vị cho bé như sau: Trong ~N~ ngày liên tiếp, mỗi ngày bé đến lớp cô sẽ đưa ra một giỏ kẹo. Giỏ kẹo ngày thứ ~i~ có ~x_i~ viên. Mỗi ngày đến lớp, bé có thể thực hiện một trong ba thao tác sau:

1. Lấy toàn bộ số kẹo trong giỏ cho vào túi riêng và giữ lại chiếc giỏ không có kẹo đó để trả lại cho cô vào các ngày sau. Bé chỉ được thực hiện thao tác lấy giỏ kẹo khi:

   • Bé đang không giữ giỏ không có kẹo nào.

   • Hoặc hôm qua bé vừa thực hiện hành động lấy giỏ kẹo và số giỏ không có kẹo hiện tại bé đang giữ nhỏ hơn ~M~.

2. Nếu bé đang giữ ~K~ giỏ ~(K > 0)~ không có kẹo và số kẹo hiện có trong túi riêng không nhỏ hơn ~C~, bé có thể trả lại cho cô đúng ~1~ giỏ không có kẹo và ~C~ viên kẹo trong túi.

3. Bé không làm gì cả (không nhận thêm giỏ cũng không trả lại).

Các thao tác được thực hiện sao cho kết thúc ngày ~N~, bé không giữ chiếc giỏ nào.

Yêu cầu: Hãy tính số kẹo nhiều nhất bé có thể có trong túi sau khi kết thúc trò chơi.

Input

• Dòng đầu ghi ba số nguyên ~N, M, C~ là số ngày của trò chơi, số giỏ không có kẹo tối đa bé có thể giữ, số kẹo phải trả lại khi thực hiện thao tác trả giỏ ~(2 \le N \le 10000; 1 \le M \le 500; 1 \le C \le 1000)~.

• ~N~ dòng sau, mỗi dòng chứa một số nguyên ~x_i~ là số kẹo trong giỏ ngày ~i~ ~(1 \le x_i \le 1000)~.

Output

Một số nguyên duy nhất là số kẹo lớn nhất bé An có thể đạt được.

Scoring

Sample Input 1

5 2 5
8
4
6
18
5

Sample Output 1

16

Notes

• Ngày ~1~: lấy giỏ ~1~, tổng ~8~.

• Ngày ~2~: bỏ ~1~ giỏ, mất ~5~, còn ~3~.

• Ngày ~3~: không lấy.

• Ngày ~4~: lấy giỏ (~18~), tổng ~21~.

• Ngày ~5~: bỏ ~1~ giỏ, mất ~5~, tổng ~16~.

Kết thúc ngày ~5~ bé An không giữ giỏ nào, số kẹo tối đa là ~16~.