시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB111100.000%

문제

Consider the following game. You have an integer matrix of size $N \times M$. Your task is to put $M$ tokens at some cells of the matrix such as:

  1. each column contains exactly one token;
  2. difference $D_r$ between the maximum and minimum number of tokens in one row is minimum possible;
  3. among all such token placements, select one such that the maximum value in a matrix cell with a token is minimum possible.

입력

The first line of input contains two integers $N$ and $M$ ($1 \le N, M \le 110$). Then matrix $a_i$ comes: $N$ lines, each containing $M$ integers $a_{i,j}$ ($1 \le a_{i,j} \le 10^9$).

출력

Print two integers which describe the placement you found: the minimum possible value of $D_r$ and the minimum value in a matrix cell with a token.

예제 입력 1

3 3
1 2 3
2 1 2
3 2 1

예제 출력 1

0
1

예제 입력 2

3 5
1 2 3 4 5
5 4 3 2 1
4 3 2 1 5

예제 출력 2

1
2