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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int MAX = 1 << 8;
const int INF = 1e9;
const LL LINF = 1e18;

struct Edge {
	int x, y;
	int c, f;
	LL p;
};

vector<Edge> E;
vector<int> g[MAX];
int N;
LL D[MAX];
int Par[MAX];
int T[MAX];
int Q[MAX];

void addEdge(int x, int y, int c, LL p) {
	g[x].push_back(SZ(E));
	E.push_back({x, y, c, 0, p});
	g[y].push_back(SZ(E));
	E.push_back({y, x, 0, 0, -p});
}

pair<int, LL> Flow(int s, int t) {
	int flow = 0;
	LL price = 0;
	while (true) {
		FOR(i, 0, N) {
			D[i] = LINF;
			Par[i] = -1;
			T[i] = 0;
		}
		T[s] = 1;
		D[s] = 0;
		Q[0] = s;
		int qh = 0, qt = 1;
		while (qh != qt) {
			int x = Q[qh++];
			if (qh == N) {
				qh = 0;
			}
			FOR(i, 0, SZ(g[x])) {
				int e = g[x][i];
				if (E[e].f == E[e].c) {
					continue;
				}
				int to = E[e].y;
				LL p = E[e].p;
				if (D[to] > D[x] + p) {
					D[to] = D[x] + p;
					Par[to] = e;
					if (T[to] == 0) {
						Q[qt++] = to;
						if (qt == N) {
							qt = 0;
						}
					}
					if (T[to] == 2) {
						qh--;
						if (qh == -1) {
							qh = N - 1;
						}
						Q[qh] = to;
					}
					T[to] = 1;
				}
			}
			T[x] = 2;
		}
		if (Par[t] == -1) {
			break;
		}
		int x = t;
		int f = INF;
		LL p = 0;
		while (x != s) {
			int e = Par[x];
			p += E[e].p;
			f = min(f, E[e].c - E[e].f);
			x = E[e].x;
		}
		x = t;
		while (x != s) {
			int e = Par[x];
			E[e].f += f;
			E[e ^ 1].f -= f;
			x = E[e].x;
		}
		flow += f;
		price += p * f;
	}
	return {flow, price};
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	int s = 0, t = 2 * n + 2;
	N = 2 * n + 3;
	FOR(i, 1, n + 1) {
		addEdge(2 * i - 1, 2 * i, 1, -INF);
		addEdge(2 * i, 2 * n + 1, 1, 0);
	}
	addEdge(2 * n + 1, t, k, 0);
	FOR(i, 0, n) {
		FOR(j, i + 1, n + 1) {
			int cost;
			cin >> cost;
			addEdge(2 * i, 2 * j - 1, 1, cost);
		}
	}
	auto [flow, price] = Flow(s, t);
	cout << price + (LL)n * INF << "\n";
	return 0;
}