






'''simple docstring'''



def  __UpperCAmelCase						(					)	->      list[list[int]]:

   """simple docstring"""
   return [list(range(1000 - i,       -1000 - i,       -1     )     ) for i in range(1000     )]


__UpperCamelCase   :							List[Any]         =   generate_large_matrix()
__UpperCamelCase   :							Tuple         =   (
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						list[list[int]]     )	->      None:

   """simple docstring"""
   assert all(row == sorted(SCREAMING_SNAKE_CASE__,       reverse=SCREAMING_SNAKE_CASE__     ) for row in grid     )
   assert all(list(SCREAMING_SNAKE_CASE__     ) == sorted(SCREAMING_SNAKE_CASE__,       reverse=SCREAMING_SNAKE_CASE__     ) for col in zip(*SCREAMING_SNAKE_CASE__     )     )



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						list[int]     )	->      int:

   """simple docstring"""
   __a					  =     0
   __a					  =     len(SCREAMING_SNAKE_CASE__     ) - 1

   # Edge cases such as no values or all numbers are negative.
   if not array or array[0] < 0:
      return 0

   while right + 1 > left:
      __a					  =     (left + right) // 2
      __a					  =     array[mid]

      # Num must be negative and the index must be greater than or equal to 0.
      if num < 0 and array[mid - 1] >= 0:
         return mid

      if num >= 0:
         __a					  =     mid + 1
      else:
         __a					  =     mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
   return len(SCREAMING_SNAKE_CASE__     )



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						list[list[int]]     )	->      int:

   """simple docstring"""
   __a					  =     0
   __a					  =     len(grid[0]     )

   for i in range(len(SCREAMING_SNAKE_CASE__     )     ):
      __a					  =     find_negative_index(grid[i][:bound]     )
      total += bound
   return (len(SCREAMING_SNAKE_CASE__     ) * len(grid[0]     )) - total



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						list[list[int]]     )	->      int:

   """simple docstring"""
   return len([number for row in grid for number in row if number < 0]     )



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						list[list[int]]     )	->      int:

   """simple docstring"""
   __a					  =     0
   for row in grid:
      for i, number in enumerate(SCREAMING_SNAKE_CASE__     ):
         if number < 0:
            total += len(SCREAMING_SNAKE_CASE__     ) - i
            break
   return total



def  __UpperCAmelCase						(					)	->      None:

   """simple docstring"""
   from timeit import timeit

   print('Running benchmarks'     )
   __a					  =     (
       'from __main__ import count_negatives_binary_search, '
       'count_negatives_brute_force, count_negatives_brute_force_with_break, grid'
   )
   for func in (
       "count_negatives_binary_search",  # took 0.7727 seconds
       "count_negatives_brute_force_with_break",  # took 4.6505 seconds
       "count_negatives_brute_force",  # took 12.8160 seconds
   ):
      __a					  =     timeit(f"""{func}(grid=grid)""",       setup=SCREAMING_SNAKE_CASE__,       number=500     )
      print(f"""{func}() took {time:0.4f} seconds"""     )


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 benchmark()







'''simple docstring'''



import os



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str = "matrix.txt"     )	->      int:

   """simple docstring"""
   with open(os.path.join(os.path.dirname(SCREAMING_SNAKE_CASE__     ),       SCREAMING_SNAKE_CASE__     )     ) as in_file:
      __a					  =     in_file.read()

   __a					  =     [[int(SCREAMING_SNAKE_CASE__     ) for cell in row.split(','     )] for row in data.strip().splitlines()]
   __a					  =     [[0 for cell in row] for row in grid]
   __a					  =     len(grid[0]     )

   __a					  =     [[0 for i in range(SCREAMING_SNAKE_CASE__     )] for j in range(SCREAMING_SNAKE_CASE__     )]
   __a					  =     grid[0][0]
   for i in range(1,       SCREAMING_SNAKE_CASE__     ):
      __a					  =     grid[0][i] + dp[0][i - 1]
   for i in range(1,       SCREAMING_SNAKE_CASE__     ):
      __a					  =     grid[i][0] + dp[i - 1][0]

   for i in range(1,       SCREAMING_SNAKE_CASE__     ):
      for j in range(1,       SCREAMING_SNAKE_CASE__     ):
         __a					  =     grid[i][j] + min(dp[i - 1][j],       dp[i][j - 1]     )

   return dp[-1][-1]


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