output_description: Print Joisino's maximum possible eventual happiness.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 A_2 ... A_{N-1}
      B_{1,1} B_{1,2} ... B_{1,M}
      B_{2,1} B_{2,2} ... B_{2,M}
      :
      B_{N,1} B_{N,2} ... B_{N,M}
attempt: import sys
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  # 二分探索木の代わり BST HST
  # 存在しない要素に対するremoveはこないことを仮定している
  
  from heapq import heappop as hpp, heappush as hp
  
  
  class HST:
      def __init__(self, ascending=True):
          self._h = []
          self._q = []
          self.ascending = ascending
  
      def push(self, v):
          if not self.ascending:
              v *= -1
          hp(self._h, v)
  
      def remove(self, v):
          if not self.ascending:
              v *= -1
          hp(self._q, v)
  
      def top(self):
          while self._q and self._q[0] == self._h[0]:
              hpp(self._q)
              hpp(self._h)
          if not self._h:
              res = None
          else:
              res = self._h[0]
              if not self.ascending:
                  res *= -1
          return res
  
  
  # inputna
  n, m = list(map(int, input().split()))
  a = list(map(int, input().split()))
  b = [list(map(int, input().split())) for _ in range(n)]
  ans = 0
  hs = [HST(ascending=False) for _ in range(m)]
  j = 0
  val = 0
  prv = 0
  
  
  def sub():
      return sum(hs[i].top() for i in range(m))
  
  
  for i in range(n):
      if i >= 1:
          val += a[i - 1]
      for k in range(m):
          hs[k].push(b[i][k])
  ans = sub() - val
  l = 0
  r = n - 1
  for _ in range(n - 1):
      for k in range(m):
          hs[k].remove(b[l][k])
      val -= a[l]
      v1 = sub() - val
  
      for k in range(m):
          hs[k].push(b[l][k])
      val += a[l]
  
      val -= a[r - 1]
      for k in range(m):
          hs[k].remove(b[r][k])
      v2 = sub() - val
      if v1 > v2:
          for k in range(m):
              hs[k].push(b[r][k])
          val += a[r - 1]
  
          val -= a[l]
          for k in range(m):
              hs[k].remove(b[l][k])
          l += 1
      else:
          r -= 1
      ans = max(ans, v1, v2)
  print(ans)
  
problem_description: Statement
  
  There are N barbecue restaurants along a street. The restaurants are numbered
  1 through N from west to east, and the distance between restaurant i and
  restaurant i+1 is A_i.
  
  Joisino has M tickets, numbered 1 through M. Every barbecue restaurant offers
  barbecue meals in exchange for these tickets. Restaurant i offers a meal of
  _deliciousness_ B_{i,j} in exchange for ticket j. Each ticket can only be used
  once, but any number of tickets can be used at a restaurant.
  
  Joisino wants to have M barbecue meals by starting from a restaurant of her
  choice, then repeatedly traveling to another barbecue restaurant and using
  unused tickets at the restaurant at her current location. Her eventual
  _happiness_ is calculated by the following formula: "(The total deliciousness
  of the meals eaten) - (The total distance traveled)". Find her maximum
  possible eventual happiness.
samples: [{"input": "3 4\n    1 4\n    2 2 5 1\n    1 3 3 2\n    2 2 5 1", "output": "11\n    \n\nThe eventual happiness can be maximized by the following strategy: start from\nrestaurant 1 and use tickets 1 and 3, then move to restaurant 2 and use\ntickets 2 and 4.\n\n* * *"}, {"input": "5 3\n    1 2 3 4\n    10 1 1\n    1 1 1\n    1 10 1\n    1 1 1\n    1 1 10", "output": "20"}]