// 题目: P2662 牛场围栏
// 链接: https://www.luogu.com.cn/problem/P2662
// 难度: 提高+/省选−
// 题解:
// - 洛谷: https://www.luogu.com.cn/problem/solution/P2662
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
ll a[maxn], head[maxn], k = 0, n, m, t;
bool vis[maxn];
ll dis[maxn];

struct edge {
    int to, next;
    ll w;
} g[maxn];

void add(int u, int v, ll w) {
    g[++k].to = v;
    g[k].next = head[u];
    g[k].w = w;
    head[u] = k;
}

void spfa(int s) {
    memset(dis, 0x7f, sizeof(dis));
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = g[i].next) {
            int v = g[i].to;
            if (dis[v] > dis[u] + g[i].w) {
                dis[v] = dis[u] + g[i].w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

void best_coder() {
    cin >> n >> m;
    t = 0x7ffffff;
    n = n * (m + 1);
    for (int i = 1; i <= n; i += m + 1) {
        cin >> a[i];
        t = min(t, a[i] - m);
        for (int j = 1; j <= m; ++j) {
            a[i + j] = a[i] - j;
        }
    }
    for (int i = 0; i < t; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[j] != t) {
                add(i, (i + a[j]) % t, a[j]);
            }
        }
    }
    spfa(0);
    ll ans = 0;
    for (int i = 1; i < t; ++i) {
        if (dis[i] > 1e8) {
            cout << -1;
            return;
        }
        ans = max(ans, dis[i] - t);
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}