Một ngày nọ, nqson mua một cây sen đá và anh ấy cần phải biết cách chăm sóc chúng. Nếu sen đá của nqson bị tưới quá $w$ ml nước trong mọi khoảng $t$ ngày liên tiếp, sen đá sẽ chết. Ví dụ: có thể tưới cho sen đá tối đa 100ml nước trong khoảng 3 ngày liên tiếp thì lượng nước nqson có thể tưới trong ngày 1 + ngày 2 + ngày 3 $\le$ 100ml, tương tự ngày 2 + ngày 3 + ngày 4 $\le$ 100ml và các ngày tiếp theo (các ngày trước ngày $t$ mà tưới quá chắc bay luôn rồi).

Tuy nhiên, trời mưa cũng có thể cung cấp nước cho cây. Cho biết $n$ ngày, mỗi ngày "đẹp trời" sẽ cung cấp cho cây của nqson $a_i$ ml nước, nqson có thể tưới tối đa cho cây của mình bao nhiêu ml nước trong $n$ ngày đó.

Đầu vào

Dòng đầu tiên chứa 3 số tự nhiên $n,w,t$ khác 0

Dòng tiếp theo chứa n số tự nhiên $a_i$

Đầu ra

Lượng nước nhiều nhất trên lý thuyết mà nqson có thể tưới cho cây. Testcase đảm bảo cây sẽ không chết vì mưa

Giới hạn

$t\le n\le {10}^6$

$t,a_i\le {10}^5$

$w\le {10}^9$

Ví dụ 1

Đầu vào

8 10 3
3 0 0 2 1 4 1 4

Đầu ra

11

Giải thích

nqson có thể tưới:
7ml nước vào ngày 2,
1ml nước vào ngày 4,
2ml nước vào ngày 5,
1ml nước vào ngày 7.