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.