import os


def    a__       (						__UpperCamelCase = "input.txt" ):

      with open(os.path.join(os.path.dirname(__UpperCamelCase )   ,					__UpperCamelCase ) ) as input_file:
            SCREAMING_SNAKE_CASE_      =     [
                [int(__UpperCamelCase ) for element in line.split("," )]
                for line in input_file.readlines()
            ]

      SCREAMING_SNAKE_CASE_      =     len(__UpperCamelCase )
      SCREAMING_SNAKE_CASE_      =     len(matrix[0] )

      SCREAMING_SNAKE_CASE_      =     [[-1 for _ in range(__UpperCamelCase )] for _ in range(__UpperCamelCase )]
      for i in range(__UpperCamelCase ):
            SCREAMING_SNAKE_CASE_      =     matrix[i][0]

      for j in range(1   ,					__UpperCamelCase ):
            for i in range(__UpperCamelCase ):
                  SCREAMING_SNAKE_CASE_      =     minimal_path_sums[i][j - 1] + matrix[i][j]

            for i in range(1   ,					__UpperCamelCase ):
                  SCREAMING_SNAKE_CASE_      =     min(
                      minimal_path_sums[i][j]   ,					minimal_path_sums[i - 1][j] + matrix[i][j] )

            for i in range(rows - 2   ,					-1   ,					-1 ):
                  SCREAMING_SNAKE_CASE_      =     min(
                      minimal_path_sums[i][j]   ,					minimal_path_sums[i + 1][j] + matrix[i][j] )

      return min(minimal_path_sums_row[-1] for minimal_path_sums_row in minimal_path_sums )


if __name__ == "__main__":
      print(f"{solution() = }")



def    a__       (						__UpperCamelCase ):
      if not head:
            return True
      # split the list to two parts
      SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_      =     head.next, head
      while fast and fast.next:
            SCREAMING_SNAKE_CASE_      =     fast.next.next
            SCREAMING_SNAKE_CASE_      =     slow.next
      SCREAMING_SNAKE_CASE_      =     slow.next
      SCREAMING_SNAKE_CASE_      =     None  # Don't forget here! But forget still works!
      # reverse the second part
      SCREAMING_SNAKE_CASE_      =     None
      while second:
            SCREAMING_SNAKE_CASE_      =     second.next
            SCREAMING_SNAKE_CASE_      =     node
            SCREAMING_SNAKE_CASE_      =     second
            SCREAMING_SNAKE_CASE_      =     nxt
      # compare two parts
      # second part has the same or one less node
      while node:
            if node.val != head.val:
                  return False
            SCREAMING_SNAKE_CASE_      =     node.next
            SCREAMING_SNAKE_CASE_      =     head.next
      return True


def    a__       (						__UpperCamelCase ):
      if not head or not head.next:
            return True

      # 1. Get the midpoint (slow)
      SCREAMING_SNAKE_CASE_      =     SCREAMING_SNAKE_CASE_      =     SCREAMING_SNAKE_CASE_      =     head
      while fast and fast.next:
            SCREAMING_SNAKE_CASE_   ,       SCREAMING_SNAKE_CASE_      =     fast.next.next, slow.next

      # 2. Push the second half into the stack
      SCREAMING_SNAKE_CASE_      =     [slow.val]
      while slow.next:
            SCREAMING_SNAKE_CASE_      =     slow.next
            stack.append(slow.val )

      # 3. Comparison
      while stack:
            if stack.pop() != cur.val:
                  return False
            SCREAMING_SNAKE_CASE_      =     cur.next

      return True





def    a__       (						__UpperCamelCase ):
      if not head or not head.next:
            return True
      SCREAMING_SNAKE_CASE_      =     {}
      SCREAMING_SNAKE_CASE_      =     0
      while head:
            if head.val in d:
                  d[head.val].append(__UpperCamelCase )
            else:
                  SCREAMING_SNAKE_CASE_      =     [pos]
            SCREAMING_SNAKE_CASE_      =     head.next
            pos += 1
      SCREAMING_SNAKE_CASE_      =     pos - 1
      SCREAMING_SNAKE_CASE_      =     0
      for v in d.values():
            if len(__UpperCamelCase ) % 2 != 0:
                  middle += 1
            else:
                  SCREAMING_SNAKE_CASE_      =     0
                  for i in range(0   ,					len(__UpperCamelCase ) ):
                        if v[i] + v[len(__UpperCamelCase ) - 1 - step] != checksum:
                              return False
                        step += 1
            if middle > 1:
                  return False
      return True


