output_description: Print the maximum possible sum of the absolute differences between the
  adjacent elements after arranging the given integers in a row in any order you
  like.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1
      :
      A_N
attempt: #! /usr/bin/env python
  # -*- coding: utf-8 -*-
  # vim:fenc=utf-8
  #
  
  """
  tenka1-2018 E
  """
  
  from itertools import product
  from itertools import combinations
  
  h, w = map(int, input().split())
  slili = [list(input()) for i in range(h)]
  
  coinsetli = [set() for i in range(h + w)]
  for i, j in product(range(h), range(w)):
      if slili[i][j] == "#":
          coinsetli[i + j + 1].add(j - i)
  
  coinacumdictli = [{} for i in range(h + w)]
  for i in range(1, h + w):
      tmp = 0
      for j in range(-300, 301):
          if j in coinsetli[i]:
              tmp += 1
          coinacumdictli[i][j] = tmp
  
  ansdouble = 0
  for i in range(1, h + w):
      for x, y in combinations(coinsetli[i], 2):
          j = abs(x - y)
          x, y = (min(x, y), max(x, y))
          if i - j >= 1:
              ansdouble += (
                  coinacumdictli[i - j][y]
                  + coinacumdictli[i - j][y - 1]
                  - coinacumdictli[i - j][x]
                  - coinacumdictli[i - j][x - 1]
              )
          if i + j <= h + w - 1:
              ansdouble += (
                  coinacumdictli[i + j][y]
                  + coinacumdictli[i + j][y - 1]
                  - coinacumdictli[i + j][x]
                  - coinacumdictli[i + j][x - 1]
              )
  
  # repeat after reversing along the vertical axis
  for i in range(h):
      slili[i].reverse()
  
  coinsetli = [set() for i in range(h + w)]
  for i, j in product(range(h), range(w)):
      if slili[i][j] == "#":
          coinsetli[i + j + 1].add(j - i)
  
  coinacumdictli = [{} for i in range(h + w)]
  for i in range(1, h + w):
      tmp = 0
      for j in range(-300, 301):
          if j in coinsetli[i]:
              tmp += 1
          coinacumdictli[i][j] = tmp
  
  for i in range(1, h + w):
      for x, y in combinations(coinsetli[i], 2):
          j = abs(x - y)
          x, y = (min(x, y), max(x, y))
          if i - j >= 1:
              ansdouble += (
                  coinacumdictli[i - j][y]
                  + coinacumdictli[i - j][y - 1]
                  - coinacumdictli[i - j][x]
                  - coinacumdictli[i - j][x - 1]
              )
          if i + j <= h + w - 1:
              ansdouble += (
                  coinacumdictli[i + j][y]
                  + coinacumdictli[i + j][y - 1]
                  - coinacumdictli[i + j][x]
                  - coinacumdictli[i + j][x - 1]
              )
  
  print(ansdouble // 2)
  
problem_description: Statement
  
  You are given N integers; the i-th of them is A_i. Find the maximum possible
  sum of the absolute differences between the adjacent elements after arranging
  these integers in a row in any order you like.
samples: [{"input": "5\n    6\n    8\n    1\n    2\n    3", "output": "21\n    \n\nWhen the integers are arranged as 3,8,1,6,2, the sum of the absolute\ndifferences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6\n- 2| = 21. This is the maximum possible sum.\n\n* * *"}, {"input": "6\n    3\n    1\n    4\n    1\n    5\n    9", "output": "25\n    \n\n* * *"}, {"input": "3\n    5\n    5\n    1", "output": "8"}]