#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

using uint = unsigned int;
using ull = unsigned long long;

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const int N = 35005;

ll dp[2][3*N];

ll mat[N][7];

int BIL = 1'000'000'000;

const int K = 7;

#define body(j) for(int p = 0; p < K; p++) {  if(p <= 2*k) dp[cur^1][j+p] = min(dp[cur^1][j+p], dp[cur][j] + mat[i][p]); } j++;

void solve(){
    int n, k;
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= 2*k; j++) {
            cin >> mat[i][j];
            mat[i][j] -= BIL;
        }
    }

    int cur = 0;
    for(int i = 0; i < n; i++) {
        memset(dp[cur^1], 0, sizeof(dp[cur^1]));
        if(i % 1000 == 0){
            debug(i);
        }
        int llim = max(0, 2*k*i-n*k);
        int rlim = min(n*k, 2*k*i);
        int j = llim;
        while(j & 3 && j <= rlim) {
            body(j)
        }
        while(j + 4 <= rlim) {
            body(j)
        }
        while(j <= rlim) {
            body(j)
        }
        cur ^= 1;
    }
    cout << dp[cur][n*k] + (ll)BIL * n << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}