#include <bits/stdc++.h>

#define Max(_A, _B) (_A > _B ? _A : _B)
#define Min(_A, _B) (_A < _B ? _A : _B)

int W[1000010][18], P[1000010][18], Log[100010];
int n, m;
int tr(int x, int y){ return (x - 1) * n + y - 1; }
long long S[1 << 18], Lazy[1 << 18], a[100010], Ans;
void Pd(int u)
{
	if(Lazy[u])
	{
		S[u << 1] += Lazy[u]; Lazy[u << 1] += Lazy[u];
		S[u << 1 | 1] += Lazy[u]; Lazy[u << 1 | 1] += Lazy[u];
		Lazy[u] = 0;
	}
}
void MD(int u, int Ls, int Rs, int l, int r, long long val)
{
	if(l <= Ls && Rs <= r) 
	{
		S[u] += val;
		Lazy[u] += val;
		return ;
	}
	Pd(u);
	int Mid = Ls + Rs >> 1;
	if(l <= Mid) MD(u << 1, Ls, Mid, l, r, val);
	if(r > Mid) MD(u << 1 | 1, Mid + 1, Rs, l, r, val);
	S[u] = Max(S[u << 1], S[u << 1 | 1]);
}
long long QU(int u, int Ls, int Rs, int l, int r)
{
	if(l <= Ls && Rs <= r) return S[u];
	Pd(u);
	int Mid = Ls + Rs >> 1; long long t1 = 0, t2 = 0;
	if(l <= Mid) t1 = QU(u << 1, Ls, Mid, l, r);
	if(r > Mid) t2 = QU(u << 1 | 1, Mid + 1, Rs, l, r);
	return Max(t1, t2);
}
std::stack<int> Q[5010];
int RMQ_Pos(int l, int r, int p)
{
	int len = Log[r - l + 1], ll = tr(p, l), rr = tr(p, r - (1 << len) + 1);
	//printf("| %d %d [%d] [%d]| -> (%d %d) (%d %d)\n", l, r, ll, rr, W[ll][len], P[ll][len], W[rr][len], P[rr][len]);
	if(W[ll][len] > W[rr][len]) return P[ll][len];
	return P[rr][len];
}
int RMQ_Val(int l, int r, int p)
{
	int len = Log[r - l + 1], ll = tr(p, l), rr = tr(p, r);
	return Max(W[ll][len], W[rr - (1 << len) + 1][len]);
}
int main()
{

	scanf("%d %d", &n, &m);
	for(int i = 1; i < n; ++i) scanf("%lld", &a[i]);
	for(int i = 1; i < n; ++i) MD(1, 1, n, i + 1, n, -a[i]);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			int t = tr(j, i);
			scanf("%d", &W[t][0]);
			P[t][0] = i;
		}
	for(int i = 1; i <= m; ++i)
		for(int j = 1; 1 << j <= n; ++j)
			for(int k = 1; k + (1 << j - 1) <= n; ++k)
			{
				int l = tr(i, k), r = tr(i, k + (1 << j - 1));
			//	printf("%d = %d [<%d, %d> <%d, %d> [%d %d]]\n", i, j, k, l, k + (1 << j), r, W[l][j - 1], W[r][j - 1]);
				W[l][j] = Max(W[l][j - 1], W[r][j - 1]);
				if(W[l][j - 1] > W[r][j - 1]) P[l][j] = P[l][j - 1];
				else P[l][j] = P[r][j - 1];
			}
	/*for(int i = 1; i <= m; ++i, puts("\n"))
		for(int j = 1; j <= n; ++j, puts(""))
			for(int k = 0; 1 << k <= n; ++k)
				printf("%d[%d %d = %d] ", W[tr(i, j)][k], i, j, tr(i, j));*/
	//puts("#");
	for(int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
	for(int i = 1; i <= m; ++i) Q[i].push(n + 1);
	/*for(int i = 1; i <= n; ++i, puts(""))
		for(int j = 1; j <= m; ++j)
			printf("%d ", W[tr(j, i)][0]);*/
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= m; ++j)
		{
			if(Q[j].top() < i)
			{
				Q[j].pop();
			//	printf("[%d %d] = %d\n", i, j, W[tr(j, i - 1)][0]);
				MD(1, 1, n, i, Q[j].top() - 1, -W[tr(j, i - 1)][0]);
			}
			while(Q[j].top() != i)
			{
			//	puts("@");
				int p = RMQ_Pos(i, Q[j].top() - 1, j), v = RMQ_Val(i, Q[j].top() - 1, j);
			//	printf("%d = (%d %d)\n", j, p, Q[j].top() - 1);
				MD(1, 1, n, p, Q[j].top() - 1, v); Q[j].push(p); 
			}
		}
	//	for(int j = 1; j <= m; ++j) printf("%d ", Q[j].top()); puts("");
		long long tmp = QU(1, 1, n, i, n);
		//printf("%lld\n", tmp);
		Ans = Max(Ans, tmp);
		MD(1, 1, n, 1, n, a[i]);
	}
	printf("%lld\n", Ans);
	return 0;
}

Measured memory_bytes: 148096