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

using namespace std;

const long long INF = 1e18;

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;

    vector<long long> R(n);
    for (int i = 0; i < n; i++) cin >> R[i];

    // A lehetséges sor-kombinációk száma (2^N)
    int num_masks = 1 << n;
    
    // total_costs[mask]: A teljes kerítés (eddig feldolgozott oszlopok) költsége,
    // ha a sorokat a 'mask' szerint festjük le globálisan.
    // Kezdetben csak a sorok kifestésének költségét (R) adjuk hozzá.
    vector<long long> total_costs(num_masks, 0);

    for (int g = 0; g < num_masks; g++) {
        long long row_cost = 0;
        for (int i = 0; i < n; i++) {
            if ((g >> i) & 1) row_cost += R[i];
        }
        total_costs[g] = row_cost;
    }

    // Segédváltozók a ciklushoz, hogy ne foglaljunk memóriát minden körben
    // current_col_prices[l][r]: az aktuális oszlopban az l-től r-ig tartó szakasz ára
    vector<vector<long long>> current_col_prices(n + 1, vector<long long>(n + 1));
    vector<long long> dp(n + 1);

    // Végigmegyünk az összes oszlopon (streaming feldolgozás)
    for (int j = 0; j < m; j++) {
        
        // 1. Beolvassuk az aktuális oszlop árait
        // A feladat szerint a sorrend: (1,1), (1,2)...(1,N), (2,2)...(2,N) stb.
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) {
                cin >> current_col_prices[l][r];
            }
        }

        // 2. Minden lehetséges sor-maszkra kiszámoljuk, mennyibe kerül ez az oszlop
        for (int g = 0; g < num_masks; g++) {
            
            // DP inicializálása: dp[r] a minimális költség az oszlop 1..r sorainak lefedésére
            for(int k=0; k<=n; k++) dp[k] = INF;
            dp[0] = 0;

            for (int r = 1; r <= n; r++) {
                // 'A' opció: Ha az r-edik sor benne van a globális maszkban,
                // akkor ezt a cellát "ingyen" átléphetjük (a költséget már a total_costs-ban hozzáadtuk).
                // A bitműveletnél (r-1), mert a maszk 0-tól indexelt, a ciklus 1-től.
                if ((g >> (r - 1)) & 1) {
                    dp[r] = dp[r - 1];
                }

                // 'B' opció: Kifestünk egy függőleges szakaszt [l, r] ebben az oszlopban.
                // Megnézzük az összes lehetséges l kezdőpontot.
                for (int l = 1; l <= r; l++) {
                    if (dp[l - 1] != INF) {
                         // Ha l-1-ig el tudtunk jutni, akkor hozzáadjuk a mostani szakasz árát
                        long long current_segment_cost = current_col_prices[l][r];
                        if (dp[l - 1] + current_segment_cost < dp[r]) {
                            dp[r] = dp[l - 1] + current_segment_cost;
                        }
                    }
                }
            }
            
            // Hozzáadjuk az oszlop minimum költségét (dp[n]) az adott maszkhoz
            total_costs[g] += dp[n];
        }
    }

    // A végén kiválasztjuk a legolcsóbb megoldást a maszkok közül
    long long best_total = INF;
    for (int g = 0; g < num_masks; g++) {
        if (total_costs[g] < best_total) {
            best_total = total_costs[g];
        }
    }

    cout << best_total << endl;

    return 0;
}