import bisect N,M = list(map(int,input().split())) D = [list(map(int,input().split())) for _ in range(N)] def check(n): for i in range(M): MIN = D[0][i] MAX = D[0][i] flag = True for j in range(1,N): left = bisect.bisect_left(D[j], MIN) right = bisect.bisect_left(D[j], MAX + n + 1) if(left == right): flag = False break MIN = D[j][left] MAX = D[j][right - 1] if(flag):return True return False if(not check(10**9)): print(-1) exit() ng,ok = -1,10**9 while(ok - ng > 1): mid = (ok+ng)//2 if(check(mid)): ok = mid else: ng = mid print(ok)