대표 선수 Batch Compilation commands

KOI 중학교에는 $N$개의 학급이 있으며, 각 학급의 학생 수는 모두 명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.

이 경기는 한반에서 한명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최대값과 최소값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, $N=3$, $M=4$인 경우 학생들의 능력치가 1반=[12, 16, 67, 43], 2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각 선택하면, 최대값과 최소값의 차이가 17-15=2로 최소가 된다.

대표로 선발된 모든 학생들 능력치의 최대값과 최소값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.

프로그램의 실행시간은 1.5초를 넘을 수 없으며, 각 데이터에 대해 부분 점수는 주어지지 않는다.

입력 형식

입력의 첫 번째 줄에는 학급의 수를 나타내는 $N$과 각 학급의 학생의 수를 나타내는 $M$이 하나의 빈칸을 사이에 두고 주어진다. 두 번째 줄부터 $N$개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 $M$개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다. 능력치는 $0$ 이상 $10^{9}$ 이하이다.

출력 형식

대표로 선발된 모든 학생들 능력치의 최대값과 최소값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력한다.

서브태스크

각 서브태스크의 점수는 맞은 데이터의 개수에 비례하게 주어집니다.

서브태스크 1 (25점)

$1 \le N, M \le 30$

서브태스크 2 (25점)

$1 \le N, M \le 500$

서브태스크 3 (50점)

$1 \le N, M \le 1,000$

입력과 출력의 예

예제 1

입력

3 4
12 16 67 43
7 17 68 48
14 15 77 54

출력

2

예제 2

입력

4 3
10 20 30
40 50 60
70 80 90
100 110 120

출력

70