#include <bits/stdc++.h>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
    read(x);
    read(y...);
}
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
typedef long long ll;
const ll inf = 1e18;
int n, k, s, t;
struct edge
{
    int v;
    ll w, c;
    int inv;
};
vector<edge> a[520];
ll dis[520];
ll d[520][520];
int cur[520];
bool in[520];
ll max_flow;
ll min_cost;
void add(int u, int v, int w, int c)
{
    int Su = a[u].size(), Sv = a[v].size();
    a[u].push_back({v, w, c, Sv});
    a[v].push_back({u, 0, -c, Su});
}
bool spfa(int s, int t)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(cur, 0, sizeof(cur));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    in[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        in[u] = 0;
        for (auto [v, w, c, j] : a[u])
        {
            if (dis[v] > dis[u] + c && w > 0)
            {
                dis[v] = dis[u] + c;
                if (!in[v])
                    q.push(v), in[v] = 1;
            }
        }
    }
    return dis[t] < 0x3f3f3f3f3f3f3f3f;
}
ll dfs(int u, int t, ll flow)
{
    if (u == t)
        return flow;
    in[u] = 1;
    for (int i = cur[u]; i < a[u].size(); i++)
    {
        auto [v, w, c, j] = a[u][cur[u] = i];
        if (!in[v] && dis[v] == dis[u] + c && w > 0)
        {
            ll tmp = dfs(v, t, min(w, flow));
            if (tmp)
                return in[u] = 0, min_cost += tmp * c, a[u][i].w -= tmp, a[v][j].w += tmp, tmp;
            dis[v] = 0x3f3f3f3f3f3f3f3f;
        }
    }
    in[u] = 0;
    return 0;
}
void dinic()
{
    ll flow = 0;
    while (spfa(s, t))
        while (flow = dfs(s, t, inf))
            max_flow += flow;
}
int main()
{
    read(n, k);
    s = 0;
    t = n + n + 2;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            int w;
            read(w);
            d[i][j] = w;
        }
    }
    ll ans = inf;
    for (int lim = 0; lim <= k; lim++)
    {
        for (int i = 0; i <= t; i++)
            a[i].clear();
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                int w = d[i][j];
                add(i + n + 1, j, 1, w);
            }
        }
        for (int i = 1; i <= n; i++)
            add(i, i + n + 1, 1, -1e9);
        for (int i = 1; i <= n; i++)
            add(i + n + 1, t, 1, 0);
        add(s, s + n + 1, lim, 0);
        memset(cur, 0, sizeof(cur));
        memset(in, 0, sizeof(in));
        dinic();
        chkmn(ans, min_cost);
        max_flow = min_cost = 0;
    }
    cout << ans + (ll)(1e9) * n << endl;
    return 0;
}