N,M = list(map(int,input().split())) D = [sorted(map(int,input().split())) for _ in range(N)] def check(n): dp = [[False for _ in range(M)] for _ in range(N)] dp[0] = [True for _ in range(M)] for i in range(N-1): ptr = 0 for j in range(M): if(ptr == M):break if(not dp[i][j]):continue while(ptr < M and D[i+1][ptr] - D[i][j] <= n): if(D[i][j] <= D[i+1][ptr]):dp[i+1][ptr] = True ptr += 1 return any(dp[-1]) 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)