#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

// Egy ajánlat tárolása: mely biteket (sorokat) fedi le, és mennyiért
struct Offer {
    int mask;
    long long cost;
};

int main() {
    // I/O gyorsítás
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Sorok globális festési költségei
    vector<long long> R(n);
    for (int i = 0; i < n; i++) cin >> R[i];

    int num_masks = 1 << n; // 2^N (pl. 4 esetén 16)
    
    // total_costs[mask]: Mennyibe kerül a kerítés eddigi része, 
    // ha a 'mask'-ban jelölt sorokat globálisan (R áron) festjük le.
    vector<long long> total_costs(num_masks, 0);

    // Kezdetben beállítjuk a globális sor-költségeket
    for (int g = 0; g < num_masks; g++) {
        long long current_row_cost = 0;
        for (int i = 0; i < n; i++) {
            if ((g >> i) & 1) current_row_cost += R[i];
        }
        total_costs[g] = current_row_cost;
    }

    // Segédváltozók (hogy ne allokáljunk mindig újra)
    vector<Offer> offers;
    offers.reserve(n * (n + 1) / 2);
    vector<long long> col_dp(num_masks);

    // Végigmegyünk az összes oszlopon
    for (int j = 0; j < m; j++) {
        offers.clear();
        
        // 1. Ajánlatok beolvasása és bitmaszkká alakítása
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) {
                long long cost;
                cin >> cost;
                
                // Maszk készítése: az l..r bitek 1-esek
                int segment_mask = 0;
                for (int k = l; k <= r; k++) {
                    segment_mask |= (1 << (k - 1));
                }
                offers.push_back({segment_mask, cost});
            }
        }

        // 2. Belső DP: "Set Cover" probléma az adott oszlopra (N=4 miatt nagyon gyors)
        // Megkeressük, mi a legolcsóbb módja bármely 'mask' lefedésének az ajánlatokból.
        // Mivel az ajánlatok átfedhetnek, ez a legbiztosabb módszer.
        
        fill(col_dp.begin(), col_dp.end(), INF);
        col_dp[0] = 0;

        // Mivel a bitek csak bővülhetnek, elég egyszer végigmenni a maszkokon 0-tól felfelé.
        for (int mask = 0; mask < num_masks; mask++) {
            if (col_dp[mask] == INF) continue;

            for (const auto& offer : offers) {
                int next_mask = mask | offer.mask;
                // Ha olcsóbban elérjük az új állapotot (akár átfedéssel is), frissítjük
                if (col_dp[mask] + offer.cost < col_dp[next_mask]) {
                    col_dp[next_mask] = col_dp[mask] + offer.cost;
                }
            }
        }

        // 3. Hozzáadjuk a legjobb oszlop-megoldásokat a globális állapotokhoz
        int full_mask = num_masks - 1;
        
        for (int g = 0; g < num_masks; g++) {
            // Mely sorok hiányoznak globálisan? (amiket nem festettünk R áron)
            // Ezeket kötelező ebben az oszlopban lefesteni.
            int needed_mask = full_mask ^ g;
            
            // Keressük a legolcsóbb belső megoldást, ami lefedi a 'needed_mask'-ot.
            // Fontos: Olyan maszk is jó, ami TÖBBET fed le, mint ami kell!
            // (Pl. csak a 2. sor kell, de az 1-2. sor festése a legolcsóbb).
            
            long long best_local_cost = INF;
            for (int s = 0; s < num_masks; s++) {
                // Ha az 's' maszk tartalmazza az összes szükséges bitet
                if ((s & needed_mask) == needed_mask) {
                    if (col_dp[s] < best_local_cost) {
                        best_local_cost = col_dp[s];
                    }
                }
            }
            
            if (total_costs[g] != INF && best_local_cost != INF) {
                total_costs[g] += best_local_cost;
            } else {
                total_costs[g] = INF;
            }
        }
    }

    // A legkisebb végösszeg kiválasztása
    long long final_ans = INF;
    for (int g = 0; g < num_masks; g++) {
        final_ans = min(final_ans, total_costs[g]);
    }

    cout << final_ans << endl;

    return 0;
}