유저 그룹 나누기

유저의 레벨이 $1$부터 $N$까지 있는 RPG 게임에 대해서, 레벨 $i$인 유저의 수 $U_i$가 주어진다. 레벨 $i$인 유저의 수 $U_i$는 $X$보다 크거나 같고 $2X$보다 작거나 같음이 보장된다.

유저를 $K$ 개의 그룹으로 나누려 한다. 같은 레벨인 유저는 같은 그룹에 속해야만 하며, 각 $K$ 개의 그룹은 연속한 레벨의 유저로 구성되어야 한다. 또한, 각 유저는 정확히 하나의 그룹에 속해야 한다.

가장 많은 유저가 속한 그룹의 유저 수와 가장 적은 유저가 속한 그룹의 유저 수의 차이를 최소화하도록 $K$ 개의 그룹으로 나누었을 때의 차이를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 세 개의 정수 $N$, $K$, $X$가 공백으로 구분되어 주어진다. $(1 \le K \le N \le 400;$ $1 \le X \le 1\,000\,000\,000)$

다음 줄에 $N$ 개의 정수 $U_i$가 공백으로 구분되어 주어진다. $(X \le U_i \le 2X)$

출력 형식

첫 줄에 $K$ 개의 그룹으로 나누었을 때, 가장 많은 유저가 속한 그룹의 유저 수와 가장 적은 유저가 속한 그룹의 유저 수 차이의 최솟값을 출력한다.

예제

7 2 1
1 1 2 1 1 1 2

1

예제 설명

레벨 $1$ 이상 $3$ 이하인 유저들을 그룹 $1$로, 레벨 $4$ 이상 $7$ 이하인 유저들을 그룹 $2$로 배정하면, $4$명의 유저들이 그룹 $1$에 있게 되고 $5$명의 유저들이 그룹 $2$에 있게 된다.

이때, 가장 많은 유저가 속한 그룹의 유저 수와 가장 적은 유저가 속한 그룹의 유저 수의 차이는 $1$이 되고, 이보다 차이가 작은 그룹 구성은 존재하지 않는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설