#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define ull unsigned long long
typedef long long ll;
#define lowbit(x) ((x) & -(x))

const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e5 + 5, M = 1e5 + 10;
typedef pair<int, int> PII;
double T = 1 >> 30;
// double PI = acos(-1);

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

void solve()
{
    int i, j;

    int n, m;
    cin >> n >> m;

    vector<int> w(n + 2);
    vector<vector<int>> val(n + 1, vector<int>(m + 1));

    for (i = 1; i <= n; i++)
    {
        cin >> w[i];
        for (j = 1; j <= min(m, n - i + 1); j++)
        {
            cin >> val[i][j];
        }
    }

    int res = INF;
    vector<int> dp(n + 5, 1e18);
    dp[1] = w[1];
    for (i = 1; i <= n; i++)
    {
        for (j = max(1ll, i - m); j < i; j++)
        {
            dp[i] = min(dp[i], dp[j] + w[i] - val[j][i - j]);
        }
        if (i + m > n)
        {
            res = min(res, dp[i] - val[i][n - i + 1]);
        }
    }

    cout << res;
}

signed main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
    int t = 1;

    //  cin >> t;

    while (t--)
    {
        //  Case++;
        solve();
    }


    return 0;
}