오렌지 출하

Juicy Orange Industry(JOI)는 맛있는 오렌지를 상자에 포장해 출하하는 회사다.

JOI는 모아 둔 오렌지 $N$개를 상자에 담아 출하한다. 먼저 오렌지를 공장의 컨베이어 벨트 위에 한 줄로 놓는다. 벨트 위의 오렌지에는 앞에서부터 차례로 $1$번부터 $N$번까지 번호가 붙어 있고, $i$번 오렌지의 크기는 $A_i$이다.

다음으로 오렌지를 앞에서부터 순서대로 상자에 나누어 담는다. 한 상자에 담는 오렌지의 번호는 연속해야 한다.

한 상자에는 오렌지를 최대 $M$개까지 담을 수 있다. 상자 하나에 오렌지를 담는 비용은 $K + s \times (a - b)$이다. 여기서 $a$는 그 상자에 담은 오렌지 크기의 최댓값, $b$는 최솟값, $s$는 담은 오렌지의 개수다. $K$는 상자를 포장하는 비용이고 모든 상자에 똑같이 적용된다.

컨베이어 벨트 위에 놓인 오렌지의 정보, 한 상자에 담을 수 있는 오렌지 개수의 최댓값, 상자를 포장하는 비용 $K$가 주어질 때 오렌지를 모두 포장하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 오렌지의 개수 $N$ ($1 \le N \le 20\,000$), 한 상자에 담을 수 있는 오렌지 개수의 최댓값 $M$ ($1 \le M \le 1\,000$, $M \le N$), 상자를 포장하는 비용 $K$ ($0 \le K \le 1\,000\,000\,000$)가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 오렌지의 크기 $A_i$ ($1 \le A_i \le 1\,000\,000\,000$)가 순서대로 한 줄에 하나씩 주어진다.

첫째 줄에 오렌지를 모두 포장하는 비용의 최솟값을 출력한다.