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. Do nó là thực vật mọng nước, sen đá của nqson cần phải được cung cấp tối thiểu $w$ ml nước trong mọi khoảng $t$ ngày liên tiếp. Ví dụ: sen đá cần ít nhất 20ml nước trong khoảng 3 ngày liên tiếp thì lượng nước nqson cần tưới trong ngày 1 + ngày 2 + ngày 3 $\ge$ 20ml, tương tự ngày 2 + ngày 3 + ngày 4 $\ge$ 20ml và các ngày tiếp theo (coi các ngày trước ngày thứ $t$ không cần tưới).

Tuy nhiên, trời mưa cũng có thể cung cấp nước cho cây, vì vậy nqson không cần phải tưới cây liên tục. 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. Nhưng nước sẽ bị bốc hơi 1ml sau mỗi ngày (bao gồm cả nước mưa và nước tưới cây). Ví dụ khi nqson tưới 5ml nước vào ngày 1, sang ngày 2, lượng nước lưu trữ từ ngày 1 giảm đi 1ml, tức còn 4ml. Chú ý: Lượng nước lưu trữ của từng ngày được tính riêng.

Hãy cho biết nqson cần phải tưới ít nhất cho cây của mình bao nhiêu ml nước trong $n$ ngày đó.

Ví dụ chi tiết: 
Lượng nước mưa từ ngày 1 đến ngày 6 lần lượt là: 5 3 8 2 0 1

nước ngày   1 | 2 | 3 | 4 | 5 | 6
ngày 1:     5   -   -   -   -   -   
ngày 2:     4   3   -   -   -   -
ngày 3:     3   2   8   -   -   -  | ngày 1 + ngày 2 + ngày 3 = 13
ngày 4:     2   1   7   2   -   -  | ngày 2 + ngày 3 + ngày 4 = 10
ngày 5:     1   0   6   1   0   -  | ngày 3 + ngày 4 + ngày 5 = 7
ngày 6:     0   0   5   0   0   1  | ngày 4 + ngày 5 + ngày 6 = 1

Đầ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 ít nhất trên lý thuyết mà nqson cần phải tưới cho cây.

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

6 7 3
5 3 8 2 0 1

Đầu ra

6

Giải thích

Dựa theo bảng trên, nqson chỉ cần tưới 6ml nước vào ngày 6.