/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //@formatter:off #pragma GCC optimize("Ofast") #include using namespace std; //@formatter:off #define rep(i, n) for (int i = 0; i < (n); ++i) #define drep(i, n) for (int i = (n)-1; i >= 0; --i) #define srep(i, s, t) for (int i = s; i < t; ++i) #define rng(a) a.begin(), a.end() #define rrng(a) a.rbegin(), a.rend() using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VVVI = vector; using VVVVI = vector; using VL = vector; using VVL = vector; using VVVL = vector; using VVVVL = vector; using VP = vector

; using VVP = vector>; using VS = vector; using VC = vector; using VVC = vector>; using VD = vector; using VVD = vector>; using VVVD = vector; using I_I = pair; const int INF = (int)1e9 + 10; // int max > 2*10^9 const long long INFL = (ll)2e18 + 10; // ll max > 9*10^18 const int JU_5 = 100000; const int JU_6 = 1000000; const ll JU_9 = 1000000000; const ll JU_18 = JU_9*JU_9; #define YES cout << "YES" << endl #define NO cout << "NO" << endl #define Yes cout << "Yes" << endl #define No cout << "No" << endl template pair operator+(const pair &a, const pair &b) { return make_pair(a.first + b.first, a.second + b.second); } template pair operator-(const pair &a, const pair &b) { return make_pair(a.first - b.first, a.second - b.second); } template pair operator*(const pair &a, const pair &b) { return make_pair(a.first * b.first, a.second * b.second); } template pair operator/(const pair &a, const pair &b) { return make_pair(a.first / b.first, a.second / b.second); } // #define MOD 1000000007 #define MOD 998244353 #define pmod(x,y) ((x%y)+y)%y /********** libs **********/ //@formatter:off // jhelper 用変数 ostream *__cout; istream *__cin; void _init_io(std::istream &cin, std::ostream &cout) { // 入出力高速化用 ios::sync_with_stdio(false); cin.tie(nullptr); cout << std::setprecision(30); // jhelper 用 __cout = &cout; __cin = &cin; } //@formatter:off /* デバッグ用 出力 */ template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v: vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } // print like python // src: https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed ///////////////////////////////////////////////////////// void print() { *__cout << endl; } template void print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; print(forward(tail)...); } template void print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } *__cout << endl; } template void print(vector> &df) { for (auto &vec: df) { print(vec); } } // endl なし void Print() {} template void Print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; Print(forward(tail)...); } template void Print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } } //@formatter:off /* * org: https://atcoder.jp/contests/abc213/submissions/24901856 * jhelper で使用するため, 全部 cin での入力にしている. (現状のレベルでは困らないので) */ template void scan(T& a){ *__cin >> a; } template void scan(vector&); template void scan(pair&); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } void in(){} template void in(T&... a){ (void)initializer_list{ (scan(a), 0)... }; } #define let_v(type,name,...) vectorname(__VA_ARGS__) #define let_V(type,name,size) vectorname(size);in(name) #define let_vv(type,name,h,...) vector>name(h,vector(__VA_ARGS__)) #define let_VV(type,name,h,w) vector>name(h,vector(w));in(name) #define let_vvv(type,name,h,w,...) vector>>name(h,vector>(w,vector(__VA_ARGS__))) #define let_vvvv(type,name,h,w,x,...) vector>>>name(h,vector>>(w,vector>(x,vector(__VA_ARGS__)))) /* string 入力を vector で受け取るみたいな */ vector let_CharVec() { string s; *__cin >> s; return {s.begin(), s.end()}; } //@formatter:off //ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } template bool chmax(T& a, C b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, C b) { if (a > b) { a = b; return true; } return false; } template T sum(const vector& v) { T res = 0; for (size_t i = 0; i < v.size(); ++i) res += v[i]; return res; } template T min(T a, C b) { return a <= b ? a : T(b); } template T max(T a, C b) { return a >= b ? a : T(b); } template vector> idx_pair(vector &vals) { vector> ans; rep(i, vals.size()) { ans.emplace_back(vals[i], i); } return ans; } /* ids 順に並び替え */ template vector sort_with_ids(vector &vals,vector &ids){ vector res; for(int i = 0;i int argmax(vector &vals){ if(vals.size()==0)return -1; int res=0; for(int i = 1;ivals[res])res=i; } return res; } template int argmin(vector &vals){ if(vals.size()==0)return -1; int res=0; for(int i = 1;i> t; while (t--) _solve(cin, cout); } //@formatter:on void _solve(std::istream &cin, std::ostream &cout) { // code int n, m; cin >> n >> m; let_VV(ll, a, n, m); rep(i, n)sort(rng(a[i])); auto n_fnc = [&](ll mid) { VI mem(m + 1, 1); rep(i, n - 1) { VI nxt(m + 1, 0); rep(j, m) { if (mem[j] <= 0)continue; int l = lower_bound(rng(a[i + 1]), a[i][j]) - a[i + 1].begin(); int r = upper_bound(rng(a[i + 1]), a[i][j] + mid) - a[i + 1].begin(); nxt[l] += 1; nxt[r] -= 1; } rep(j, m) { nxt[j + 1] += nxt[j]; } swap(mem, nxt); } rep(i, m) { if (mem[i] > 0)return true; } return false; }; ll l = -1, r = INF +10; while (l + 1 < r) { ll mid = (l + r) / 2; if (n_fnc(mid)) r = mid; else l = mid; } if(r>=INF){ print(-1);return; } print(r); } }; int main() { No2157 solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }