Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Elongated Matrix

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a matrix $$$a$$$, consisting of $$$n$$$ rows and $$$m$$$ columns. Each cell contains an integer in it.

You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be $$$s_1, s_2, \dots, s_{nm}$$$.

The traversal is $$$k$$$-acceptable if for all $$$i$$$ ($$$1 \le i \le nm - 1$$$) $$$|s_i - s_{i + 1}| \ge k$$$.

Find the maximum integer $$$k$$$ such that there exists some order of rows of matrix $$$a$$$ that it produces a $$$k$$$-acceptable traversal.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 16$$$, $$$1 \le m \le 10^4$$$, $$$2 \le nm$$$) — the number of rows and the number of columns, respectively.

Each of the next $$$n$$$ lines contains $$$m$$$ integers ($$$1 \le a_{i, j} \le 10^9$$$) — the description of the matrix.

Output

Print a single integer $$$k$$$ — the maximum number such that there exists some order of rows of matrix $$$a$$$ that it produces an $$$k$$$-acceptable traversal.

Examples

Input

4 2 9 9 10 8 5 3 4 3

Output

5

Input

2 4 1 2 3 4 10 3 7 3

Output

0

Input

6 1 3 6 2 5 1 4

Output

3

Note

In the first example you can rearrange rows as following to get the $$$5$$$-acceptable traversal:

5 3

10 8

4 3

9 9

Then the sequence $$$s$$$ will be $$$[5, 10, 4, 9, 3, 8, 3, 9]$$$. Each pair of neighbouring elements have at least $$$k = 5$$$ difference between them.

In the second example the maximum $$$k = 0$$$, any order is $$$0$$$-acceptable.

In the third example the given order is already $$$3$$$-acceptable, you can leave it as it is.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2019 08:06:09 (e3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|