import sys #input = sys.stdin.readline #input = sys.stdin.buffer.readline #文字列はダメ sys.setrecursionlimit(1000000) import math import bisect #import itertools #import random #from heapq import heapify, heappop, heappush from collections import defaultdict from collections import deque #import copy #DeepCopy: hoge = [_[:] for _ in hogehoge] #from functools import lru_cache #@lru_cache(maxsize=None) #MOD = pow(10,9) + 7 MOD = 998244353 #dx = [1,0,-1,0] #dy = [0,1,0,-1] #dx8 = [1,1,0,-1,-1,-1,0,1] #dy8 = [0,1,1,1,0,-1,-1,-1] class SegmentTree(object): def __init__(self, A, dot, unit): n = 1 << (len(A) - 1).bit_length() tree = [unit] * (2 * n) for i, v in enumerate(A): tree[i + n] = v for i in range(n - 1, 0, -1): tree[i] = dot(tree[i << 1], tree[i << 1 | 1]) self._n = n self._tree = tree self._dot = dot self._unit = unit def __getitem__(self, i): return self._tree[i + self._n] def update(self, i, v): i += self._n self._tree[i] = v while i != 1: i >>= 1 self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1]) def add(self, i, v): self.update(i, self[i] + v) def sum(self, l, r): #これで[l,r)から取り出す。 l += self._n r += self._n l_val = r_val = self._unit while l < r: if l & 1: l_val = self._dot(l_val, self._tree[l]) l += 1 if r & 1: r -= 1 r_val = self._dot(self._tree[r], r_val) l >>= 1 r >>= 1 return self._dot(l_val, r_val) def main(): N,M = map(int,input().split()); INF = 1<<60 D = [list(map(int,input().split())) for _ in range(N)] for i in range(N): D[i].sort() def check(x): Tree = SegmentTree([x]*M,min,INF) for i in range(1,N): # output # output = [Tree[j] for j in range(M)] # print("output",output) NTree = SegmentTree([INF]*M,min,INF) preDi = [-INF] + D[i-1] # print(preDi) left = 0; right = 0 for j in range(M): # left = bisect.bisect_left(preDi,D[i][j] - x) # right = bisect.bisect_right(preDi,D[i][j]) while left < M+1 and preDi[left] < D[i][j] - x: left += 1 while right < M+1 and preDi[right] <= D[i][j]: right += 1 val = Tree.sum(left-1, right-1) # print(left,right,val) if val <= x: NTree.update(j,x) NTree,Tree = Tree,NTree # output = [Tree[j] for j in range(M)] # print("output",output) # print("handan",Tree.sum(0,M)) if Tree.sum(0,M) <= x: return True else: return False ok = pow(10,9) ng = -1 while abs(ok-ng) > 1: mid = (ok+ng)//2 if check(mid): ok = mid else: ng = mid if ok == pow(10,9): print(-1) else: print(ok) if __name__ == '__main__': main()