지도

바이트랜드가 행정 구역을 새로 나눈 뒤, 지도 제작소는 나라의 새 인구 분포 지도를 만들고 있다. 기술적인 이유로 쓸 수 있는 색은 몇 가지뿐이다. 인구(주민 수)가 같거나 비슷한 지역끼리 같은 색을 갖도록 지도를 칠해야 한다.

색 $k$에 대하여, 값 $A(k)$를 다음을 만족하도록 정한다.

• 색 $k$로 칠한 지역 중 적어도 절반은 인구가 $A(k)$ 이하이고,
• 색 $k$로 칠한 지역 중 적어도 절반은 인구가 $A(k)$ 이상이다.

즉 $A(k)$는 색 $k$로 칠한 지역들의 인구의 중앙값이다.

색 $k$로 칠한 한 지역의 칠하기 오차는 $|A(k) - p|$이며, 여기서 $p$는 그 지역의 인구이다. 누적 오차는 모든 지역의 칠하기 오차를 모두 더한 값이다. 누적 오차가 가장 작아지는 최적의 칠하기를 찾는다.

바이트랜드 각 지역의 인구를 읽어 최소 누적 오차를 계산한 뒤 표준 출력에 쓰는 프로그램을 작성하라.

첫째 줄에 지역의 수 $n$이 주어지며, $10 < n < 3000$이다.

둘째 줄에 지도를 칠하는 데 사용하는 색의 수 $m$이 주어지며, $2 \le m \le 10$이다.

이어지는 $n$개의 줄에는 각 줄마다 한 지역의 인구를 나타내는 음이 아닌 정수가 하나씩 주어진다. 어떤 인구도 $2^{30}$을 넘지 않는다.

최적으로 칠했을 때 얻을 수 있는 최소 누적 오차를 정수 하나로 한 줄에 출력한다.