#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int INF = 1e9;

struct Edge
{
    int from, to, capacity, cost;
    Edge(int f, int t, int ca, int co) : from(f), to(t), capacity(ca), cost(co) {}
};

vector<vector<int>> adj, cost, capacity;

void shortest_paths(int n, int v0, vector<int>& d, vector<int>& p) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<bool> inq(n, false);
    queue<int> q;
    q.push(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int v : adj[u]) {
            if (capacity[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
                d[v] = d[u] + cost[u][v];
                p[v] = u;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int min_cost_flow(int N, vector<Edge> edges, int K, int s, int t) {
    adj.assign(N, vector<int>());
    cost.assign(N, vector<int>(N, 0));
    capacity.assign(N, vector<int>(N, 0));
    for (Edge e : edges) {
        adj[e.from].push_back(e.to);
        adj[e.to].push_back(e.from);
        cost[e.from][e.to] = e.cost;
        cost[e.to][e.from] = -e.cost;
        capacity[e.from][e.to] = e.capacity;
    }

    int flow = 0;
    int cost = 0;
    vector<int> d, p;
    while (flow < K) {
        shortest_paths(N, s, d, p);
        if (d[t] == INF)
            break;

        // find max flow on that path
        int f = K - flow;
        int cur = t;
        while (cur != s) {
            f = min(f, capacity[p[cur]][cur]);
            cur = p[cur];
        }

        // apply flow
        flow += f;
        cost += f * d[t];
        cur = t;
        while (cur != s) {
            capacity[p[cur]][cur] -= f;
            capacity[cur][p[cur]] += f;
            cur = p[cur];
        }
    }

    if (flow < K)
        return -1;
    else
        return cost;
}


void solve() {
    int N, M; cin >> N >> M;
    vector<vi> amt(N, vi(M));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> amt[i][j];
        }
    }
    vector<vi> am(N, vi(N));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> am[i][j];
            if(am[i][j] == -1) am[i][j] = INF;
        }
    }
    for(int k = 0; k < N; k++)
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                if(am[i][k] < INF && am[k][j] < INF)
                    am[i][j] = min(am[i][j], am[i][k] + am[k][j]);
    int numV = 2 + N + M;
    vector<Edge> edges;
    for(int i = 0; i < M; i++) {
        edges.emplace_back(0, i + 1, 1, 0);
        for(int j = 0; j < N; j++) {
            int cost = 0;
            for(int k = 0; k < N; k++) {
                cost += amt[k][i] * am[k][j];
            }
            edges.emplace_back(i + 1, j + M + 1, 1, cost);
        }
    }
    for(int i = 0; i < N; i++) {
        edges.emplace_back(i + M + 1, numV - 1, 1, 0);
    }
    cout << min_cost_flow(numV, edges, M, 0, numV - 1) << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}