問題文

毎朝開催されるバーチャルコンテスト「あさかつ」では $N$ 問の問題がそれぞれ決まった難易度帯から出題されます．

隣り合う問題の難易度の差は 崖 と呼ばれ、一般的に崖が大きいことはあまり好まれません．

なので、問題を選定する時は崖を小さくすることが望ましいです．

次の問いは、これを一般化したものです．

$N$ 種類の難易度帯 $D_i$ に含まれる問題はそれぞれ $M$ 問あり、$D_{i,j}$ として与えられます．

これを用いて、問題のセット $A$ の各要素を次のように定義します．

• $A_i(1\leq{i}\leq{N})$ を難易度帯 $D_i$ の問題の中から一つ選ぶ．
  

ただし、 $A$ は広義単調増加列でなければなりません．

つまり、任意の $1 \leq i \leq N-1$ に対して $A_i \leq A_{i+1}$ が成り立つ必要があります．

このとき、$A$ に対して $f(A)$ を「各 $i$ に対する $A_{i+1}-A_i$ の最大値」で定めたとき、$f(A)$ の最小値を解答してください．

ただし、条件を満たす $A$ が存在しない場合は -1 を出力してください．

入力

$N\ M$ 
$D_{1,1} , D_{1,2} , \cdots , D_{1,M}$ 
$D_{2,1} , D_{2,2} , \cdots , D_{2,M}$ 
$\hspace{8pt}\vdots \hspace{19pt} \vdots  \hspace{9pt}\ddots  \hspace{11pt}\vdots$ 
$D_{N,1} , D_{N,2} , \cdots , D_{N,M}$ 

• $1\leq{N,M}\leq{1500}$
  
• $1\leq{D_{i,j}}\leq{10^9}$
  

出力

$f(A)$ の最小値を一行に出力してください．ただし，条件を満たす $A$ が存在しない場合は -1 を出力してください．

サンプル

2 2
5 8
12 7

2

4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

0

3 2
2 4
1 5
3 2

-1