#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];
}