시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB149312423.529%

문제

마왕이 쓰러졌다!

그러나 용사는 마왕의 마법으로 과거2회차로 보내졌다.

다시 한 번 마왕을 물리쳐야 하는 용사는 1회차에서의 경험으로 $K$ 명으로 구성된 최고의 팀워크를 가진 파티를 만들기로 했고, 파티의 실력 차이가 최소가 될 때 최고의 팀워크를 발휘할 수 있다고 생각했다.

파티원 중 한 명을 적절히 골라 다른 모든 파티원과의 실력 차이를 합한 값을 최소가 되도록 했을 때, 이 최솟값을 파티의 실력 차이로 정의한다. 파티원 각각의 실력을 $w_{1},w_{2}, \cdots,w_{K}$로 나타낼 때, 파티의 실력 차이를 수식으로 나타내면 다음과 같다.

\[\min_{1\le x\le K}\sum_{i=1}^{K}\lvert w_{i}-w_{x}\lvert\]

$N$명의 후보 중 $K-1$명을 선택해 용사를 포함한 $K$명의 파티원으로 구성된 파티를 만들기로 했을 때, 용사에게 최고의 팀워크를 가진 파티를 알려주자!

입력

첫 번째 줄에 공백을 사이에 두고 $N$과 $K$가 주어진다. ($1\le K-1\le N\le 1\,000\,000$)

두 번째 줄에 용사의 실력 $Y$가 주어진다. ($1\le Y\le 10^9$)

세 번째 줄에 $N$명의 파티원 후보의 실력 $v_{1},v_{2},\cdots ,v_{N}$이 공백을 사이에 두고 주어진다. ($1\le v_{i}\le 10^9$)

주어지는 모든 수는 정수이다.

출력

파티의 실력 차이의 최솟값을 출력한다.

예제 입력 1

6 4
3
6 6 1 2 2 6

예제 출력 1

2

출처

Contest > BOJ User Contest > 아니메컵 > 아니메컵 2쿨 J번