#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2")  //Enable AVX

using namespace std;

using ll = long long;

#define mp make_pair

const int p = 1000000007;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

/*const int N = 1000000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}*/

const int N = 20000;

vector<ll> t(N);
vector<ll> lazy(N);

void push(int v) {
    t[v*2] += lazy[v];
    lazy[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, ll addend) {
    if (l > r)
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}

ll query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -1e18;
    if (l <= tl && tr <= r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)),
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, m;
    cin>>n>>m;
    vector<int> a(n-1);
    for (int i = 0; i<n-1; i++) cin>>a[i];

    vector<vector<int>> b(n, vector<int>(m));
    for (int i = 0; i<n; i++)
        for (int j = 0; j<m; j++) cin>>b[i][j];

    ll answer = 0;

    vector<stack<int>> st(m);
    for (int i = 0; i<m; i++)
    {
        st[i].push(0);
        answer+=b[0][i];
    }
    update(1, 0, n-1, 0, 0, answer);

    for (int i = 1; i<n; i++)
    {
        update(1, 0, n-1, 0, i-1, -a[i-1]);
        for (int s = 0; s<m; s++)
        {
            update(1, 0, n-1, i, i, b[i][s]);
            //cout<<"s: "<<s<<endl;
            while (!st[s].empty() && b[st[s].top()][s]<=b[i][s])
            {
                int lol = st[s].top();
                st[s].pop();
                int r = 0;
                if (!st[s].empty()) r = st[s].top() + 1;
                //cout<<r<<' '<<lol-1<<' '<<b[i][s] - b[lol][s]<<endl;
                update(1, 0, n-1, r, lol, b[i][s] - b[lol][s]);
            }
            st[s].push(i);
        }
        answer = max(answer, query(1, 0, n-1, 0, n-1));
        /*cout<<i<<":"<<endl;
        for (int i = 0; i<n; i++) cout<<query(1, 0, n-1, i, i)<<' ';
        cout<<endl;*/
    }
    cout<<answer;


}

Measured memory_bytes: 6912