높이가 비슷한 텐트 자리

문제

완만한 비탈에 조성된 캠핑장에는 텐트를 설치할 수 있는 자리가 N개 있다. 각 자리에는 기준 지점보다 얼마나 높은지를 나타내는 정수 높이가 적혀 있다. 서로 다른 자리라도 높이가 같을 수 있으며, 높이가 같은 자리들도 각각 별개의 자리로 사용할 수 있다. 각 자리에는 텐트를 한 동만 설치할 수 있다. 캠핑장을 방문한 일행은 텐트 K동을 설치하려고 한다. 일행은 밤에 서로 오갈 때 높이 차이가 크지 않도록, 사용할 자리 중 가장 높은 자리와 가장 낮은 자리의 높이 차이를 작게 만들고 싶어 한다. 따라서 N개의 자리 중 정확히 K개를 선택하고, 선택한 자리들의 최대 높이에서 최소 높이를 뺀 값을 높이 차이로 정한다. 자리 사이의 실제 거리나 입력에 적힌 순서는 선택 조건에 포함하지 않는다. 입력에서 이웃한 자리끼리 골라야 하는 것도 아니다. 이 문제에서 일행이 고려하는 정보는 각 자리의 높이뿐이다. 선택하지 않은 자리의 높이는 높이 차이를 계산할 때 사용하지 않는다. 자리의 높이를 바꾸거나 한 자리에 텐트를 두 동 설치하는 것은 허용하지 않는다. 일행은 먼저 높이 차이가 가장 작아지는 선택을 찾는다. 그와 같은 최소 높이 차이를 만드는 선택이 여러 개라면, 선택한 자리들의 최소 높이가 가장 작은 선택을 사용한다. 이 두 기준까지 같다면 어느 선택을 사용해도 출력 결과가 같으므로, 자리 번호로 추가 비교할 필요는 없다. K가 1이면 선택한 자리의 최대 높이와 최소 높이가 같으므로 높이 차이는 0이다. 이때에도 동점 처리 규칙을 적용한다. K는 N 이하이므로 텐트를 설치할 자리를 고르지 못하는 경우는 없다. 자리들의 높이가 주어질 때, 규칙에 따라 선택한 자리들의 높이 차이와 최소 높이를 구한다. 선택한 모든 자리의 높이나 번호를 출력할 필요는 없다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 1,000이다. 둘째 줄에 각 자리의 높이를 나타내는 정수 H_1, H_2, …, H_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ H_i ≤ 1,000이다.

출력

최소 높이 차이와, 그 차이를 만드는 선택 중 가장 작은 최소 높이를 공백으로 구분하여 출력한다.

6 3
12 4 9 5 13 6

2 4

5 2
14 3 15 4 9

1 3

4 1
8 2 2 11

0 2

출처: Devin.KR 자체 제작