#include <bits/stdc++.h>  
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
ll MOD = 1e9 + 7;

int N_MAX = 4;
int M_MAX = 1e5;
int n, m;

vector<int> r(N_MAX + 1);
vector<vector<vector<int>>> c(M_MAX + 1, vector<vector<int>>(N_MAX + 1, vector<int>(N_MAX + 1))); 

vector<vector<vector<int>>> dpCol(M_MAX + 1, vector<vector<int>>(N_MAX + 1, vector<int>(N_MAX + 1))); 

int main()
{
	//ifstream cin("in.txt");
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> r[i];
	}

	for(int j = 1; j <= m; j++){
		for(int u = 1; u <= n; u++){
			for(int d = u; d <= n; d++){
				
				cin >> c[j][u][d];
				
			}
		}
	}

	//cout << c[1][1][2] << '\n';


	for(int j = 1; j <= m; j++){
		for(int d = 1; d <= n; d++){
			for(int u = d; u >= 1; u--){	
				dpCol[j][u][d] = c[j][u][d];
				if(u == d) 
				{
					continue;
				}

				for(int d2 = 1; d2 <= d - 1; d2++){
					dpCol[j][u][d] = min(dpCol[j][u][d], dpCol[j][u][d2] + dpCol[j][d2 + 1][d]);
				}
			}
		}
	}

	for(int j = 1; j <= m; j++){
		for(int u = 1; u <= n; u++){
			for(int d = n; d >= u; d--){
				if(u - 1 >= 1){
					dpCol[j][u][d] = min(dpCol[j][u][d], dpCol[j][u - 1][d]);
				}
				if(d + 1 <= n){
					dpCol[j][u][d] = min(dpCol[j][u][d], dpCol[j][u][d + 1]);
				}
			}
		}
	}

	/*for(int j = 1; j <= m; j++){
		cout << j << ": " << '\n';
		for(int u = 1; u <= n; u++){
			for(int d = 1; d <= n; d++){
				cout << dpCol[j][u][d] << " ";
			}
			cout << '\n';
		}
		cout << '\n';
	}*/

	int s = 0;

	vector<ll> sum(n + 1);
	vector<int> dpRow(n + 1);

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			sum[i] += dpCol[j][s + 1][i];
		}
		if(sum[i] < r[i] + dpRow[i - 1]){
			dpRow[i] = sum[i] + dpRow[s];
		}
		else{
			s = i;
			dpRow[i] = r[i] + dpRow[i - 1];
		}

		//cout << i << " " <<  sum[i] << " " << dpRow[i] << '\n';
	}

	cout << dpRow[n];




	
	




}