output_description: Print the number of possible values of S - T.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N X D
attempt: import sys
  
  input = sys.stdin.readline
  H, W = map(int, input().split())
  A = [list(map(int, input().split())) for _ in range(H)]
  B = [list(map(int, input().split())) for _ in range(H)]
  D = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]
  dp = [[{} for _ in range(W)] for _ in range(H)]
  dp[0][0][D[0][0]] = 0
  for h in range(H):
      for w in range(W):
          for v in dp[h][w]:
              if w != W - 1:
                  v1 = v + D[h][w + 1]
                  v2 = v - D[h][w + 1]
                  if v1 < 0:
                      v1 *= -1
                  if v2 < 0:
                      v2 *= -1
                  dp[h][w + 1][v1] = 0
                  dp[h][w + 1][v2] = 0
              if h != H - 1:
                  v1 = v + D[h + 1][w]
                  v2 = v - D[h + 1][w]
                  if v1 < 0:
                      v1 *= -1
                  if v2 < 0:
                      v2 *= -1
                  dp[h + 1][w][v1] = 0
                  dp[h + 1][w][v2] = 0
  ans = min(dp[H - 1][W - 1])
  print(ans)
  
problem_description: Statement
  
  We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1
  \leq i < N ) holds.
  
  Takahashi will take some (possibly all or none) of the elements in this
  sequence, and Aoki will take all of the others.
  
  Let S and T be the sum of the numbers taken by Takahashi and Aoki,
  respectively. How many possible values of S - T are there?
samples: [{"input": "3 4 2", "output": "8\n    \n\nA is (4, 6, 8).\n\nThere are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6,\n8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8),\n(6))), ((6, 8), (4))), and ((4, 6, 8), ()).\n\nThe values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18,\nrespectively, so there are eight possible values of S - T.\n\n* * *"}, {"input": "2 3 -3", "output": "2\n    \n\nA is (3, 0). There are two possible values of S - T: -3 and 3.\n\n* * *"}, {"input": "100 14 20", "output": "49805"}]