Nhân dịp đến quê hương Bắc Giang tham gia thi học sinh giỏi Hùng Vương, Kiều đến thăm trang trại trồng vải thiều của bác Thuấn. Trang trại gồm N cây trồng thẳng hàng và cách đều nhau (khoảng cách từ gốc cây i đến gốc cây i+1 bằng K với mọi i =1 ..N-1).

Năm nay, là năm được mùa nên cây nào cũng sai quả, cây thứ i có số lượng quả vải là Ai quả. Bác Thuấn rất lo lắng vì tuổi già rồi làm sao có thể hái được hết số vải thiều này, đang nghĩ cách giúp bác Thuấn thì đột nhiên có một ông tiên hiện ra trước mắt Kiều và nói: Ta cho cháu một chiếc túi thần này, cháu hãy chọn một chỗ đứng bất kỳ rồi hô to câu thần trú "Vải ơi chui vào đây" sau đó tất cả số quả vải thuộc các cây có khoảng cách từ gốc đến chỗ cháu đứng không lớn hơn H sẽ từ từ lìa khỏi cành và bay vào túi thần của cháu.

Yêu cầu: Hãy cho biết Kiều có thể hái giúp bác Thuấn được tối đa bao nhiêu quả vải nếu lời nói của ông tiên là hiện thực.

Input:

• Dòng 1: chứa 3 số nguyên dương N, K, H, các số nguyên cách nhau ít nhất một kí tự cách trống (1 ≤ N ≤ 10^6, 1 ≤ K, H ≤ 10^9 ).
• Dòng 2: chứa N số nguyên A1, A2,…, AN (Trong đó Ai là số lượng quả vải của cây vải thứ i; A[i]≤ 10^9 với 1 ≤ i ≤ N).

Output:

gồm một số nguyên duy nhất là tổng số lượng quả vài nhiều nhất mà Kiều có thể hái được.

Sample Input:

6 2 3
4 2 4 5 1 6

Sample Output

16