당신은 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가 주어져 있을 때, 상자 포장에 드는 비용 총합의 최솟값를 구하는 프로그램을 작성하라.

#3155 upload 153 done 35 how_to_reg 32

오렌지 출하 timer 2s memory 512MB

#3155

오렌지 출하 2s 512MB