강도

밤에 Joe the Elusive는 국가 중앙은행의 금고에 침입했다. 금고에는 한 줄로 배치된 칸이 n개 있으며, 각 칸에는 일정량의 다이아몬드가 들어 있다. 문제를 더 편리하게 다루기 위해 왼쪽부터 오른쪽까지 칸에 1부터 n까지의 양의 번호를 붙이자.

안타깝게도 Joe는 마지막 보안 시스템을 끄지 않았다. 다행인 점은 그 작동 방식을 알고 있다는 것이다.

보안 시스템은 매분 인접한 두 cells 각각에 있는 다이아몬드의 총량을 계산한다(두 칸의 번호 차가 1인 경우). 이 검사를 수행하면 n - 1개의 합을 얻는다. 이 합들 중 적어도 하나가 이전 검사에서 얻은 대응하는 합과 다르면 보안 시스템이 작동한다.

Joe는 보안 시스템의 검사 사이에 한 칸에서 다른 칸으로 다이아몬드를 옮길 수 있다. 두 검사 사이에 최대 m번 옮길 수 있다. 다음 세 연산 중 하나를 수행하면 다이아몬드를 한 번 옮긴 것으로 간주한다. 임의의 칸에서 다른 임의의 칸으로 다이아몬드 하나를 옮기는 것, 임의의 칸에서 Joe의 주머니로 다이아몬드 하나를 옮기는 것, Joe의 주머니에서 임의의 칸으로 다이아몬드 하나를 옮기는 것이다. Initially Joe's의 주머니는 비어 있으며, 다이아몬드를 무제한으로 담을 수 있다. Joe가 어떤 행동도 하기 전에 시스템이 적어도 한 번 검사한다고 간주한다.

아침에는 은행 직원들이 올 것이므로 Joe는 그전에 은행을 떠나야 한다. 아침까지 k분만 남았으며, 이 k분 각각에 Joe는 최대 m번의 연산을 수행할 수 있다. Joe의 주머니에 남은 것은 모두 그의 전리품으로 간주한다.

Joe가 가지고 나갈 수 있는 다이아몬드의 최대 개수를 구한다. 보안 시스템은 Joe가 은행을 떠난 뒤에도 triggered되어서는 안 되며, Joe는 아침이 되기 전에 떠나야 한다는 점을 잊지 말아야 한다.

첫째 줄에 정수 n, m, k (1 ≤ n ≤ 104, 1 ≤ m, k ≤ 109)가 주어진다. 다음 줄에는 n개의 수가 주어진다. i-th번째 수는 i-th번째 칸에 있는 다이아몬드의 양과 같으며, 0부터 105까지의 정수이다.

Joe가 훔칠 수 있는 다이아몬드의 최대 개수를 나타내는 하나의 수를 출력한다.

두 번째 예제에서 Joe는 다음과 같이 행동할 수 있다.

다이아몬드의 초기 위치는 4 1 3이다.

첫 번째 시간 구간에 Joe는 1-th번째 칸에서 2-th번째 칸으로 다이아몬드 하나를 옮기고, 3-th번째 칸에서 자신의 주머니로 다이아몬드 하나를 옮긴다.

첫 번째 시간 구간이 끝났을 때 다이아몬드의 위치는 3 2 2이다. 검사 결과 차이가 발견되지 않아 보안 시스템은 작동하지 않는다.

두 번째 시간 구간에 Joe는 3-rd번째 칸에서 2-nd번째 칸으로 다이아몬드 하나를 옮기고, 1-st번째 칸에서 자신의 주머니로 다이아몬드 하나를 옮긴다.

두 번째 시간 구간이 끝났을 때 다이아몬드의 위치는 2 3 1이다. 이번에도 검사 결과 차이가 발견되지 않아 보안 시스템은 작동하지 않는다.

Now Joe는 주머니에 다이아몬드 2개를 넣은 채 떠난다.