시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 28 15 14 63.636%

문제

당신은 Juicy Orange Industry 사를 알고 있는가? 이 회사의 업무는 맛있는 오렌지를 포장해서 출하하는 것이다. 여기서는 줄여서 JOI사라고 부르겠다.

JOI사에서는 수집된 N개의 오렌지를 상자에 넣어 출하하게 되었다. 오렌지는 공장에 있는 벨트 컨베이어 위에 나란히 놓여져서, 벨트 컨베이어 앞에서부터 순서대로 1부터 N까지 번호가 붙여져 있다. 오렌지는 크기가 지각각이어서, 오렌지 i(1≦ i ≦ N)의 크기를 Ai라 한다.

이 오렌지들을 앞에서부터 순서대로 몇 개인가 상자에 나눠 담는다. 한 상자에는 연속한 번호의 오렌지밖에 담을 수 없다.

하나의 상자에는 최대 M개까지 오렌지를 담을 수 있다. 어떤 상제에 몇 개의 오랜지를 담을 때 드는 코스트는, 상자에 담긴 가장 큰 오렌지의 크기를 a, 상자에 담긴 가장 작은 오렌지의 크기를 b, 상자에 담긴 오렌지의 개수를 s라고 할 때, K + s × (a − b)로 구할 수 있다. 여기에서 K는  상자를 포장하는 코스트로서, 모든 상자에 공통되는 수치이다.

적절한 개수의 상자를 사용해서, 모든 오렌지를 적절하게 포장하는 것으로, 상자 포장에 드는 코스트의 총합을 가능한 한 작게 하고 싶다.

벨트 컨베이어 위에 놓여져 있는 오렌지의 정보와, 한 상자에 담을 수 있는 오렌지의 개수의 최대치와, 상자를 포장하는 코스트가 주어져 있을 때, 상자 포장에 드는 코스트의 총합의 최소치를 구하는 프로그램을 작성하라.

입력

표준입력으로부터 아래의 입력을 읽어들여라.

  • 1행에는 3개의 정수 N, M, K가 공백으로 구분되어 쓰여져 있다. 이것은 오렌지가 N개 있고, 하나의 상자에 담을 수 있는 오랜지의 개수의 최대치가 M이고, 상자를 포장하는 코스트가 K라는 것을 나타낸다.
  • 이어지는 N개의 행의 i번째 행(1 ≦ i ≦ N)에는, 정수 Ai가 쓰여져 있다. 이것은 오렌지 i의 크기가 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.

출력

표준 출력에, 상자를 포장하는 코스트의 총합의 최소치를 한 줄에 출력하라.

예제 입력

6 3 6
1
2
3
1
2
1

예제 출력

21

예제 입력 2

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

예제 출력 2

164

예제 입력 3

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

예제 출력 3

177

예제 입력 4

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

예제 출력 4

10000000000

힌트

출처

Olympiad > 일본정보올림피아드 > JOI 2016 1번

  • 문제를 번역한 사람: KimJJ