output_description: Print the maximum number of candies that can be collected.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_{1, 1} A_{1, 2} ... A_{1, N}
      A_{2, 1} A_{2, 2} ... A_{2, N}
attempt: import sys
  
  input = sys.stdin.readline
  import heapq as hq
  
  n, m = map(int, input().split())
  s, t = map(int, input().split())
  abd = [list(map(int, input().split())) for i in range(m)]
  mod = 10**9 + 7
  graph = [[] for i in range(n + 1)]
  for a, b, d in abd:
      graph[a].append((b, d))
      graph[b].append((a, d))
  dists = [[10**18, 0] for i in range(n + 1)]
  distt = [[10**18, 0] for i in range(n + 1)]
  for start, dist in (s, dists), (t, distt):
      dist[start] = [0, 1]
      q = [(0, start)]
      hq.heapify(q)
      while q:
          dx, x = hq.heappop(q)
          k = dist[x][1]
          for y, d in graph[x]:
              if dist[y][0] > dx + d:
                  dist[y][0] = dx + d
                  dist[y][1] = k
                  hq.heappush(q, (dist[y][0], y))
              elif dist[y][0] == dx + d:
                  dist[y][1] = (dist[y][1] + k) % mod
  dst = dists[t][0]
  ansls = []
  for u, v, d in abd:
      for a, b in (u, v), (v, u):
          if dists[a][0] < distt[a][0]:
              if dists[a][0] * 2 < dst and distt[b][0] * 2 < dst:
                  if dists[a][0] + distt[b][0] + d == dst:
                      ansls.append(dists[a][1] * distt[b][1] % mod)
  for v in range(1, n + 1):
      if dists[v][0] * 2 == distt[v][0] * 2 == dst:
          ansls.append(dists[v][1] * distt[v][1] % mod)
  sm = sum(ansls) % mod
  ans = sm**2 % mod
  for i in ansls:
      ans = (ans - i**2) % mod
  print(ans)
  
problem_description: Statement
  
  We have a 2 \times N grid. We will denote the square at the i-th row and j-th
  column (1 \leq i \leq 2, 1 \leq j \leq N) as (i, j).
  
  You are initially in the top-left square, (1, 1). You will travel to the
  bottom-right square, (2, N), by repeatedly moving right or down.
  
  The square (i, j) contains A_{i, j} candies. You will collect all the candies
  you visit during the travel. The top-left and bottom-right squares also
  contain candies, and you will also collect them.
  
  At most how many candies can you collect when you choose the best way to
  travel?
samples: [{"input": "5\n    3 2 2 4 1\n    1 2 2 2 1", "output": "14\n    \n\nThe number of collected candies will be maximized when you:\n\n  * move right three times, then move down once, then move right once.\n\n* * *"}, {"input": "4\n    1 1 1 1\n    1 1 1 1", "output": "5\n    \n\nYou will always collect the same number of candies, regardless of how you\ntravel.\n\n* * *"}, {"input": "7\n    3 3 4 5 4 5 3\n    5 3 4 4 2 3 2", "output": "29\n    \n\n* * *"}, {"input": "1\n    2\n    3", "output": "5"}]