#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

struct Primal_Dual{
    const int INF=(1<<30);
    struct edge{
        int to,cap,cost,rev;
    };
    vector<vector<edge>> G;
    vector<int> potential,min_cost,prevv,preve;
    Primal_Dual(int V):G(V){}
    void add_edge(int s,int t,int cap,int cost){
        G[s].push_back((edge){t,cap,cost,(int)(G[t].size())});
        G[t].push_back((edge){s,0,-cost,(int)(G[s].size()-1)});
    }
    int min_cost_flow(int s,int t,int f){
        int V=G.size(); int res=0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        potential.assign(V,0);
        preve.assign(V,-1);
        prevv.assign(V,-1);
        while(f>0){
            min_cost.assign(V,INF);
            pq.push(make_pair(0,s));
            min_cost[s]=0;
            while(pq.size()){
                auto p=pq.top(); pq.pop();
                if(min_cost[p.second]<p.first)continue;
                int i=-1;
                for(auto &e:G[p.second]){
                    i++;
                    int nextcost=min_cost[p.second]+e.cost+potential[p.second]-potential[e.to];
                    if(e.cap>0 and min_cost[e.to]>nextcost){
                        min_cost[e.to]=nextcost;
                        prevv[e.to]=p.second;
                        preve[e.to]=i;
                        pq.push(make_pair(min_cost[e.to],e.to));
                    }
                }
            }
            if(min_cost[t]==INF)return -1; // 流せない
            for(int v=0;v<V;v++){
                potential[v]+=min_cost[v];
            }
            int Addflow=f;
            for(int v=t;v!=s;v=prevv[v]){
                Addflow=min(Addflow,G[prevv[v]][preve[v]].cap);
            }
            f-=Addflow;
            res+=Addflow*potential[t];
            for(int v=t;v!=s;v=prevv[v]){
                edge &e=G[prevv[v]][preve[v]];
                e.cap-=Addflow;
                G[v][e.rev].cap+=Addflow;
            }
        }
        return res;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> v[i][j];
        }
    }
    vector<vector<int>> d(n, vector<int>(n, 1e9));
    for (int i = 0; i < n; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int dd; cin >> dd;
            if (dd == -1) continue;
            d[i][j] = dd;
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }

    Primal_Dual g(n+m+2);
    int S = n+m, T = n+m+1;
    for (int i = 0; i < m; ++i) {
        g.add_edge(S, i, 1, 0);
    }
    for (int i = 0; i < n; ++i) {
        g.add_edge(i+m, T, 1, 0);
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            ll cost = 0;
            for (int k = 0; k < n; ++k) {
                cost += (ll)v[k][i]*d[k][j];
            }
            g.add_edge(i, j+m, 1, cost);
        }
    }
    cout << g.min_cost_flow(S, T, m) << endl;
}