Minimizing the Looseness of a Bike Lock

After the winter break, Little I returned to school only to find that he had forgotten the combination to his bicycle lock. The lock consists of \( n \) dials, each with \( k \) segments (with \( k \le 4 \)). The positive integer in the \( i \)th segment of the \( j \)th dial is \( a_{i,j} \).

You are allowed to rotate each dial any number of times (possibly zero). When you rotate the \( j \)th dial once, every number on that dial shifts cyclically: the number in the \( i \)th segment moves to the \( ((i \bmod k) + 1) \)th segment. In other words, treating the dials in 0-indexed form we have that after \( r \) rotations the number originally in position \( i \) moves to position \( (i+r) \bmod k \). Equivalently, after a rotation of \( r \) the number that appears in row \( i \) is \( a_{((i - r - 1 \bmod k)+1), j} \) (using 1-indexing).

For ease of remembrance, Little I requires that the numbers on the same row (after the rotations) are as close as possible. Formally, for \( 1 \le i \le k \), define the looseness of the \( i \)th row as \[ c(i) = \max_{1 \le j \le n} a_{i,j} - \min_{1 \le j \le n} a_{i,j}, \] and the overall looseness of the lock as \[ C = \max_{1 \le i \le k} c(i). \] Your task is to determine the minimum possible value of \( C \) that can be achieved by choosing an appropriate rotation for each dial.

inputFormat

The first line contains two integers \( n \) and \( k \) (\(1 \le n \le 10\) and \(1 \le k \le 4\)), representing the number of dials and the number of segments per dial.

The next \( k \) lines each contain \( n \) positive integers. In the \( i \)th line, the \( j \)th number is \( a_{i,j} \), the number in the \( i \)th segment of the \( j \)th dial (from top to bottom).

outputFormat

Output a single integer, the minimum possible overall looseness \( C \) after optimally rotating the dials.

sample

1 3
5
3
8

0