#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

const LL INF = 0x3fffffffffffffffLL;

struct LazySeg {
  int size;
  vector<char> has_lazy;
  vector<LL> seg;
  vector<LL> lazy;
  vector<LL> width;
  vector<LL> assi;

  LazySeg(vector<LL> A) {
    int n = A.size();
    size = 1;
    while (size < n) size *= 2;

    seg.resize(size);
    seg.insert(seg.end(), A.begin(), A.end());
    seg.resize(size*2);
    lazy.resize(size*2);
    has_lazy.resize(size*2);
    width.resize(size*2);
    assi.resize(size*2);
    rrep(i, size) {
      seg[i] = max(seg[i*2], seg[i*2+1]);
      width[i] = width[i*2] + width[i*2+1]; 
    }
  }

  void LazyPropagate(int k) {
    if (has_lazy[k]) {
      seg[k] = assi[k];
      if (k < size) {
        has_lazy[k*2] = true;
        has_lazy[k*2+1] = true;
        assi[k*2] = assi[k]; 
        assi[k*2+1] = assi[k];
        lazy[k*2] = 0;
        lazy[k*2+1] = 0;
      }
      has_lazy[k] = false;
    }

    seg[k] += lazy[k];
    if (k < size) {
      lazy[k*2] += lazy[k];
      lazy[k*2+1] += lazy[k];
    }
    lazy[k] = 0;
  }

  void Add(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      lazy[k] += x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Add(wishl, wishr, k*2, watchl, mid, x);
    Add(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = max(seg[k*2], seg[k*2+1]);
  }

  void Move(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      has_lazy[k] = true;
      lazy[k] = 0;
      assi[k] = x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Move(wishl, wishr, k*2, watchl, mid, x);
    Move(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = max(seg[k*2], seg[k*2+1]);
  }

  void Add(int wishl, int wishr, LL x) {
    return Add(wishl, wishr, 1, 0, size, x);
  }

  void Move(int wishl, int wishr, LL x) {
    return Move(wishl, wishr, 1, 0, size, x);
  }

  LL Get(int wishl, int wishr, int k, int watchl, int watchr) {
    LL lval, rval;

    if (wishr <= watchl || watchr <= wishl) return -INF;

    if (wishl <= watchl && watchr <= wishr) {
      LazyPropagate(k);
      return seg[k];
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    lval = Get(wishl, wishr, k*2, watchl, mid);
    rval = Get(wishl, wishr, k*2+1, mid, watchr);
    return max(lval, rval);
  }

  LL Get(int wishl, int wishr) {
    return Get(wishl, wishr, 1, 0, size);
  }
};

int N;
int M;
LL ans = 0;
LL A[5145];
LL B[5145][214];
vector<pii> decs[214];

LL Calc(int idx) {
  LL ret = 0;
  rep(i, M) {
    ret += B[idx][i];
  }
  return ret;
}

int main() {
  scanf("%d%d", &N, &M);
  reps(i, 1, N) {
    scanf("%lld", &A[i]);
  }

  rep(i, N) {
    rep(j, M) {
      scanf("%lld", &B[i][j]);
    }
  }

  LazySeg seg(vector<LL>(N, -INF/2)); 
  ans = Calc(0);
  seg.Move(0, 1, ans);
  rep(i, M) {
    decs[i].eb(pii(0x3fffffff, -1));
    decs[i].eb(pii(B[0][i], 0));
  }

  reps(i, 1, N) {
    seg.Add(0, i, -A[i]);
    rep(j, M) {
      int idx = i;

      while (1) {
        auto p = decs[j].back();
        if (p.X >= B[i][j]) break;
        decs[j].pop_back();
        int l = decs[j].back().Y + 1;
        int r = p.Y + 1;
        seg.Add(l, r, B[i][j] - p.X);
      }

      decs[j].eb(pii(B[i][j], i));
    }
    seg.Move(i, i+1, Calc(i));
    
    MX(ans, seg.Get(0, N));
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 9344