#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

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

const int MAX = 107;
const int INF = 1e9;

int u[MAX];
int v[MAX];
int p[MAX];
int way[MAX];
int minv[MAX];
bool used[MAX];

int hungarian(const vector<vector<int>>& a) {
	int n = SZ(a), m = SZ(a[0]);
	FOR(i, 0, n + 1) {
		u[i] = 0;
	}
	FOR(j, 0, m + 1) {
		v[j] = 0;
		p[j] = n;
		way[j] = 0;
	}
	FOR(i, 0, n) {
		p[m] = i;
		int j0 = m;
		FOR(j, 0, m + 1) {
			minv[j] = INF;
			used[j] = 0;
		}
		while (p[j0] != n) {
			used[j0] = true;
			int i0 = p[j0];
			int j1 = -1;
			int delta = INF;
			FOR(j, 0, m) {
				if (!used[j]) {
					int cur = a[i0][j] - u[i0] - v[j];
					if (cur < minv[j]) {
						minv[j] = cur;
						way[j] = j0;
					}
					if (minv[j] < delta) {
						delta = minv[j];
						j1 = j;
					}
				}
			}
			FOR(j, 0, m + 1) {
				if (used[j]) {
					u[p[j]] += delta;
					v[j] -= delta;
				}
				else {
					minv[j] -= delta;
				}
			}
			assert(j1 != -1);
			j0 = j1;
		}
		while (j0 != m) {
			int j1 = way[j0];
			p[j0] = p[j1];
			j0 = j1;
		}
	}
	vector<int> ans(n + 1);
	FOR(j, 0, m) {
		ans[p[j]] = j;
	}
	int res = 0;
	FOR(i, 0, n) {
		res += a[i][ans[i]];
	}
	assert(res == -v[m]);
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector b(n, vector<int>(m));
	for (auto& bi : b) {
		for (int& bij : bi) {
			cin >> bij;
		}
	}
	vector d(n, vector<int>(n));
	for (auto& di : d) {
		for (int& dij : di) {
			cin >> dij;
			if (dij == -1) {
				dij = INF;
			}
		}
	}
	FOR(k, 0, n) {
		FOR(i, 0, n) {
			FOR(j, 0, n) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	vector a(m, vector<int>(n));
	FOR(i, 0, m) {
		FOR(j, 0, n) {
			FOR(k, 0, n) {
				a[i][j] += d[j][k] * b[j][i];
			}
		}
	}
	cout << hungarian(a) << "\n";
	return 0;
}