#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

ll dp[5005][5005];
int N, M;
ll a[5005];
ll dist[5005];
ll b[200][5000];

template <typename T>
struct segtree{
    int n;
    T UNIT;
    vector<T> dat;
    vector<T> val;
    segtree(int n_, vector<int> v){
        for(int i = 0; i < n_; i++) val.push_back(v[i]);
        val.push_back(-1);
        UNIT = n_;
        n = 1;
        while(n < n_) n *= 2;
        dat = vector<T>(2*n);
        for(int i = 0; i < 2*n; i++) dat[i] = UNIT;
    }

    T calc(T a, T b){
        T ans;
        ans = (val[a] > val[b]) ? a : b;
        return ans;
    }
    void insert(int k, T a){
        dat[k+n-1] = a;
    }
    void update_all(){
        for(int i = n-2; i >= 0; i--){
            dat[i] = calc(dat[i*2+1], dat[i*2+2]);
        }
    }
    //k番目の値(0-indexed)をaに変更
    void update(int k, T a){
        k += n-1;
        dat[k] = a;
        while(k > 0){
            k = (k-1)/2;
            dat[k] = calc(dat[k*2+1], dat[k*2+2]);
        }
    }

    //[a, b)
    //区間[a, b]へのクエリに対してはquery(a, b+1)と呼ぶ
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;
        if(r <= a || b <= l) return UNIT;
        if(a <= l && r <= b) return dat[k];
        else{
            T vl = query(a, b, k*2+1, l, (l+r)/2);
            T vr = query(a, b, k*2+2, (l+r)/2, r);
            return calc(vl, vr);
        }
    }
};

void paint(int l1, int l2, int r1, int r2, ll max_val){
    dp[l1][r1] += max_val;
    dp[l2+1][r1] -= max_val;
    dp[l1][r2+1] -= max_val;
    dp[l2+1][r2+1] += max_val;
}

void calc(){
    for(int i = 0; i < N; i++){
        for(int j = 1; j < N; j++){
            dp[i][j] += dp[i][j-1];
        }
    }
    for(int i = 1; i < N; i++){
        for(int j = 0; j < N; j++){
            dp[i][j] += dp[i-1][j];
        }
    }
}

void search(int i, int l, int r, segtree<int> &sgt){
    if(l == r){
        int idx = l;
        ll max_val = b[i][idx];
        paint(l, l, r, r, max_val);
        return;
    }else if(r < l){
        return;
    }else{
        int idx = sgt.query(l, r+1);
        ll max_val = b[i][idx];
        // cout << "query:" << i << ' ' << l << '-' << r << ' ' << idx << ' ' << max_val << endl;
        paint(l, idx, idx, r, max_val);
        search(i, l, idx-1, sgt);
        search(i, idx+1, r, sgt);
        return;
    }
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N >> M;
    for(int i = 0; i < N-1; i++) cin >> a[i];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++) {
            cin >> b[j][i];
        }
    }
    for(int i = 0; i < M; i++){
        vector<int> v;
        for(int j = 0; j < N; j++) v.push_back(b[i][j]);
        segtree<int> sgt(N, v);
        for(int j = 0; j < N; j++) sgt.update(j, j);
        search(i, 0, N-1, sgt);
    }
    calc();
    for(int i = 1; i < N; i++) dist[i] = dist[i-1]+a[i-1];
    ll ans = 0;
    for(int l = 0; l < N; l++){
        for(int r = l; r < N; r++){
            ans = max(ans, dp[l][r]-dist[r]+dist[l]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 203840