#include using namespace std; #define GET_MACRO(a, b, c, NAME, ...) NAME #define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rep2(i, a) rep3 (i, 0, a) #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__) #define repr2(i, a) repr3 (i, 0, a) #define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--) template inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); } template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } using ll = long long; const int inf = 1e9; pair updateMax(pair x, int y) { vector a { x.first, x.second, y }; sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); if (a.size() == 1) { return{ a[0], -inf }; } else { return{ a[0], a[1] }; } } pair updateMin(pair x, int y) { vector a { x.first, x.second, y }; sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); reverse(a.begin(), a.end()); if (a.size() == 1) { return{ a[0], inf }; } else { return{ a[0], a[1] }; } } int main() { int n, m; cin >> n >> m; static int A[3][800]; rep(i, m) rep(j, n) cin >> A[i][j]; pair ans; rep(u, m) { ll E = 0; int *a = A[u]; vector> maxFront(1010, make_pair(-inf, -inf)); vector> minFront(1010, make_pair(inf, inf)); vector> maxBack(1010, make_pair(-inf, -inf)); vector> minBack(1010, make_pair(inf, inf)); maxFront[0] = { a[0], -inf }; minFront[0] = { a[0], inf }; maxBack[n - 1] = { a[n - 1], -inf }; minBack[n - 1] = { a[n - 1], inf }; rep(i, 1, n) { maxFront[i] = updateMax(maxFront[i - 1], a[i]); minFront[i] = updateMin(minFront[i - 1], a[i]); } repr(i, n - 1) { maxBack[i] = updateMax(maxBack[i + 1], a[i]); minBack[i] = updateMin(minBack[i + 1], a[i]); } rep(i, n) { int mn = inf, mx = -inf; rep(j, i + 1, n) { int cand = 0; if (a[i] == a[j]) continue; // case 1: k < i < j if (i > 0) { if (a[i] < a[j]) { // a[k] > a[i] and a[k] != a[j] int x, y; tie(x, y) = maxFront[i - 1]; if (x > a[i] && x != a[j]) { chmax(cand, max(x, a[j])); } else if (y > a[i] && y != a[j]) { chmax(cand, max(y, a[j])); } } else { // a[k] < a[i] and a[k] != a[j] int x, y; tie(x, y) = minFront[i - 1]; if (x < a[i] && x != a[j]) { chmax(cand, a[i]); } else if (y < a[i] && y != a[i]) { chmax(cand, a[i]); } } } // case 2: i < k < j // a[k] > max(a[i], a[j]) if (mx > max(a[i], a[j])) { chmax(cand, mx); } // a[k] < min(a[i], a[j]) if (mn < min(a[i], a[j])) { chmax(cand, max(a[i], a[j])); } // case 3: i < j < k if (j < n - 1) { if (a[i] < a[j]) { // a[k] < a[j] and a[k] != a[i] int x, y; tie(x, y) = minBack[j + 1]; if (x < a[j] && x != a[i]) { chmax(cand, a[j]); } else if (y < a[j] && y != a[i]) { chmax(cand, a[j]); } } else { // a[k] > a[j] and a[k] != a[i] int x, y; tie(x, y) = maxBack[j + 1]; if (x > a[j] && x != a[i]) { chmax(cand, max(x, a[i])); } else if (y > a[j] && y != a[i]) { chmax(cand, max(y, a[i])); } } } chmin(mn, a[j]); chmax(mx, a[j]); E += cand; } } chmax(ans, make_pair(E, -u)); } cout << -ans.second << endl; return 0; }