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

using namespace std;

// Globális tárolás a sebességért
long long ar[100001][5][5];
long long sorar[5];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 0; i < n; i++) cin >> sorar[i];

    for (int i = 1; i <= m; i++) {
        for (int y = 1; y <= n; y++) {
            for (int z = y; z <= n; z++) {
                cin >> ar[i][y][z];
            }
        }
        
        // INTERVALLUM OPTIMALIZÁLÁS (Többszörös festés kezelése)
        // Ha egy nagyobb intervallum olcsóbb, mint bármely benne lévő részintervallum,
        // akkor a részintervallumot is meg tudjuk festeni a nagyobb áráért.
        for (int len = n; len >= 1; len--) {
            for (int y = 1; y <= n - len + 1; y++) {
                int z = y + len - 1;
                // Lefelé terjesztjük az árat: a [y,z] ára érvényes a belső [y+1,z] és [y,z-1]-re
                if (y + 1 <= z) ar[i][y + 1][z] = min(ar[i][y + 1][z], ar[i][y][z]);
                if (z - 1 >= y) ar[i][y][z - 1] = min(ar[i][y][z - 1], ar[i][y][z]);
            }
        }
    }

    long long best_total = -1;

    // Összesen 2^N lehetőség (max 16)
    for (int mask = 0; mask < (1 << n); mask++) {
        long long current_sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) current_sum += sorar[i];
        }

        // Minden oszlopra kiszámoljuk a DP-t
        for (int i = 1; i <= m; i++) {
            long long dp[5]; 
            dp[0] = 0;
            for(int k = 1; k <= n; k++) dp[k] = 2e18; // Végtelen

            for (int y = 1; y <= n; y++) {
                // Opció 1: Sor már festve van globálisan
                if ((mask >> (y - 1)) & 1) {
                    dp[y] = min(dp[y], dp[y - 1]);
                }
                // Opció 2: Egy oszlop-intervallummal fejezzük be a sor lefedését
                for (int z = 1; z <= y; z++) {
                    dp[y] = min(dp[y], dp[z - 1] + ar[i][z][y]);
                }
            }
            current_sum += dp[n];
            
            // Ha már drágább mint az eddigi legjobb, ezt a maszkot eldobjuk
            if (best_total != -1 && current_sum >= best_total) break;
        }

        if (best_total == -1 || current_sum < best_total) {
            best_total = current_sum;
        }
    }

    cout << best_total << endl;

    return 0;
}