문제
당신은 Juicy Orange Industry 사를 알고 있는가? 이 회사의 업무는 맛있는 오렌지를 포장해서 출하하는 것이다. 여기서는 줄여서 JOI사라고 부르겠다.
JOI사에서는 수집된 N개의 오렌지를 상자에 넣어 출하하게 되었다. 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓여져서, 컨베이어 벨트 앞에서부터 순서대로 1부터 N까지 번호가 붙여져 있다. 오렌지는 크기가 제각각이어서, 오렌지 i(1≤i≤N)의 크기를 Ai라 한다.
이 오렌지들을 앞에서부터 순서대로 몇 개를 상자에 나눠 담는다. 한 상자에는 연속한 번호의 오렌지밖에 담을 수 없다.
또, 하나의 상자에는 최대 M개까지 오렌지를 담을 수 있다. 어떤 상자에 몇 개의 오렌지를 담을 때 드는 비용은, 상자에 담긴 가장 큰 오렌지의 크기를 a, 상자에 담긴 가장 작은 오렌지의 크기를 b, 상자에 담긴 오렌지의 개수를 s라고 할 때, K+s*(a-b)로 구할 수 있다. 여기에서 K는 상자를 포장하는 비용으로, 모든 상자에 똑같이 적용된다.
적절한 개수의 상자를 사용해서 모든 오렌지를 적절하게 포장할 때, 상자 포장에 드는 비용의 총합을 가능한 한 작게 하고 싶다.
오렌지 개수 N과 컨베이어 벨트 위에 놓여져 있는 오렌지의 정보 Ai(1≤i≤N), 한 상자에 담을 수 있는 오렌지의 개수의 최대치 M, 상자를 포장하는 코스트 K가 주어져 있을 때, 상자 포장에 드는 비용 총합의 최솟값를 구하는 프로그램을 작성하라.
입력
첫째 줄에 N, M, K가 공백을 사이에 두고 차례로 주어진다.
그 후 N개의 줄에 오렌지 크기가 주어진다.
i(1≤i≤N)째 줄에 Ai가 주어진다.
모든 입력 데이터는 아래의 조건을 만족한다.
1≤N≤20,000
1≤M≤1,000
0≤K≤1,000,000,000
1≤Ai≤1,000,000,000 (1≤i≤N)
M≤N
출력
N개의 오렌지를 포장하는 데 드는 최소 비용을 출력한다.
부분 문제
부분 문제 1 [39점]
N≤20
부분 문제 2 [30점]
N≤2,000
M≤100
부분 문제 3 [31점]
추가 제한 없음.
예제1
입력
636
1
2
3
1
2
1
출력
21
예제2
입력
16412
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19
출력
164
예제3
입력
16614
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12
출력
177
예제4
입력
1011000000000
1
1
1
1
1
1
1
1
1
1
출력
10000000000
출처
JOI 2016 본선, 2018camp contest3 problemC