은행털이

밤이 되어 Joe the Elusive는 그 나라의 중앙은행 금고에 침입했다. 금고에는 일렬로 배치된 n개의 칸이 있으며, 각 칸에는 일정량의 다이아몬드가 들어 있다. 문제를 다루기 편하도록 왼쪽부터 오른쪽까지 각 칸에 1부터 n까지의 양의 정수를 붙이자.

불행히도 Joe는 마지막 보안 시스템을 끄지 못했다. 다행인 점은 그 작동 방식을 알고 있다는 것이다.

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

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

아침이 되면 은행 직원들이 오므로 Joe는 그 전에 은행을 떠나야 한다. 아침까지는 k분밖에 남지 않았으며, 이 k분 각각에 Joe는 최대 m개의 연산을 수행할 수 있다. Joe의 주머니에 남아 있는 것은 모두 훔친 것으로 간주한다.

Joe가 가지고 나갈 수 있는 다이아몬드의 최대 개수를 구한다. 보안 시스템은 Joe가 은행을 떠난 뒤에도 작동해서는 안 되며, 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개를 넣은 채 떠난다.