Bingo

Time limit1sMemory limit512 MB

Summary

Place one token in each column of an N x M matrix, minimizing first the spread of token counts across rows, then the largest token value.

Level: Medium7 of 10
Topics: Greedy, Binary search, Sorting, Implementation
Solved: No attempts yet

Problem

Consider the following game. You have an integer matrix of size $N \times M$ . Your task is to place $M$ tokens on cells of the matrix such that:

each column contains exactly one token;
the difference $D_r$ between the maximum and minimum number of tokens in a row is as small as possible;
among all such placements, you choose one where the maximum value written in a cell that holds a token is as small as possible.

Input

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

Output

Print two integers that describe the placement you found: the minimum possible value of $D_r$ and the minimum value written in a cell that holds a token, separated by a space.

Examples2

Example 1
Input
```
3 3
1 2 3
2 1 2
3 2 1
```
Expected output
```
0
1
```
Example 2
Input
```
3 5
1 2 3 4 5
5 4 3 2 1
4 3 2 1 5
```
Expected output
```
1
2
```