파이프라인에서 $n$개의 작업을 스케줄링해야 한다. 작업들은 수열을 이루며, 작업 $i$의 작업량은 $a_i$이다. 파이프라인은 직렬로 연결된 $m$개의 단계로 이루어진다.

처리를 시작하기 전에 정수 $t$ ($0 \le t \le n$)를 선택할 수 있다. 이렇게 하면 처음 $t$개의 작업을 상대적인 순서를 바꾸지 않고 맨 뒤로 옮겨 $a_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t$를 얻는다. $t=0$ 또는 $t=n$을 선택하면 수열은 바뀌지 않는다.

그다음, 이렇게 얻은 수열을 최대 $k$개의 비어 있지 않은 연속 구간으로 나누어야 하며, 각 구간은 하나의 배치를 이룬다. 배치의 작업량은 그 배치에 속한 작업들의 작업량의 합이다.

배치들은 순서대로 파이프라인에 들어간다. 각 배치는 $1, 2, \ldots, m$ 단계를 이 순서대로 거치며, 각 단계에서 자신의 작업량과 같은 시간이 걸린다. 각 단계는 한 번에 최대 하나의 배치를 처리하며, 수열에서 배치들이 왼쪽에서 오른쪽으로 나타나는 순서를 따른다. 한 단계에서 처리가 끝난 뒤, 배치는 다음 단계가 사용 가능해질 때까지 기다릴 수 있다. 기다리는 동안에는 더 이상 이전 단계를 점유하지 않으므로, 이전 단계는 다음 배치를 처리할 수 있다. 서로 다른 단계는 서로 다른 배치를 동시에 처리할 수 있다.

파이프라인은 시각 $0$에 처리를 시작한다. 모든 작업이 가능한 한 일찍 끝나도록 옮길 접두 구간과 배치로 나누는 방법을 선택하라.

입력

첫 번째 줄에는 세 정수 $n, m, k$ ($1 \le n, m \le 5 \times 10^5$, $1 \le k \le n$)가 주어진다. 이는 각각 작업의 수, 단계의 수, 배치 수의 최댓값이다.

두 번째 줄에는 작업들의 작업량을 나타내는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$)이 주어진다.

출력

모든 작업이 끝나는 시각의 가능한 최솟값을 정수 하나로 출력하라.

예제

입력 1

4 3 2
3 1 4 2

출력 1

20

참고

최적의 선택 중 하나는 접두 구간 $[3, 1, 4]$를 맨 뒤로 옮겨 수열 $[2, 3, 1, 4]$를 얻은 뒤, 이를 두 배치 $[2, 3]$과 $[1, 4]$로 나누는 것이다. 두 배치의 작업량은 모두 $5$이다. 이들은 첫 번째 단계에서 각각 시각 $0$과 $5$에 시작하여, 세 번째 단계에서 각각 시각 $15$와 $20$에 끝날 수 있다. 따라서 모든 작업은 시각 $20$에 끝나며, 이는 가능한 최소 시각이다.