Vụ trộm kim cương

Két sắt của ngân hàng gồm $n$ ngăn xếp thành một hàng, đánh số từ $1$ đến $n$ từ trái sang phải. Ngăn thứ $i$ đang chứa $a_i$ viên kim cương.

Hệ thống an ninh hoạt động như sau: cứ mỗi phút nó tính tổng số kim cương của từng cặp ngăn kề nhau, tức là $n-1$ giá trị $a_1+a_2,a_2+a_3,\dots ,a_{n-1}+a_n$. Nếu có ít nhất một tổng khác với tổng tương ứng ở lần kiểm tra trước đó thì chuông báo động kêu. Hệ thống đã thực hiện một lần kiểm tra trước khi tên trộm bắt đầu hành động.

Giữa hai lần kiểm tra liên tiếp, tên trộm thực hiện không quá $m$ thao tác. Mỗi thao tác dưới đây được tính là một thao tác:

• chuyển một viên kim cương từ một ngăn bất kỳ sang một ngăn khác;
• chuyển một viên kim cương từ một ngăn vào túi của tên trộm;
• chuyển một viên kim cương từ túi vào một ngăn bất kỳ.

Ban đầu túi rỗng và có sức chứa không giới hạn. Hiển nhiên không thể lấy kim cương ra từ một ngăn rỗng, nên số kim cương trong mỗi ngăn luôn phải không âm.

Tên trộm chỉ còn $k$ phút trước khi trời sáng. Chuông báo động không được kêu tại bất kỳ lần kiểm tra nào, kể cả lần kiểm tra diễn ra sau khi tên trộm đã rời đi. Số kim cương còn lại trong túi chính là chiến lợi phẩm.

Hãy tính số kim cương nhiều nhất mà tên trộm có thể lấy đi.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất: số kim cương nhiều nhất tên trộm có thể lấy đi.

Ràng buộc

• $1\le n\le {10}^4$
• $1\le m,k\le {10}^9$
• $0\le a_i\le {10}^5$

Ví dụ