
'''simple docstring'''



from __future__ import annotations

_lowercase    =		list[tuple[int, int]]

_lowercase    =		[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

_lowercase    =		([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right




class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase   ,       _lowercase   ,       _lowercase   ,       _lowercase   ,       _lowercase   ,       _lowercase   ,       ):

												"""simple docstring"""



												_lowerCAmelCase  						=			pos_x
												_lowerCAmelCase  						=			pos_y
												_lowerCAmelCase  						=			(pos_y, pos_x)
												_lowerCAmelCase  						=			goal_x
												_lowerCAmelCase  						=			goal_y
												_lowerCAmelCase  						=			g_cost
												_lowerCAmelCase  						=			parent
												_lowerCAmelCase  						=			self.calculate_heuristic()




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			abs(self.pos_x - self.goal_x				)
												_lowerCAmelCase  						=			abs(self.pos_y - self.goal_y				)
												return dx + dy




						def __lt__( self   ,       _lowercase				):

												"""simple docstring"""



												return self.f_cost < other.f_cost






class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			Node(start[1]   ,       start[0]   ,       goal[1]   ,       goal[0]   ,       0   ,       _lowercase				)
												_lowerCAmelCase  						=			Node(goal[1]   ,       goal[0]   ,       goal[1]   ,       goal[0]   ,       99_999   ,       _lowercase				)

												_lowerCAmelCase  						=			[self.start]
												_lowerCAmelCase  						=			[]

												_lowerCAmelCase  						=			False




						def  _lowercase     ( self				):

												"""simple docstring"""



												while self.open_nodes:
																		# Open Nodes are sorted using __lt__
																		self.open_nodes.sort()
																		_lowerCAmelCase  						=			self.open_nodes.pop(0				)

																		if current_node.pos == self.target.pos:
																								_lowerCAmelCase  						=			True
																								return self.retrace_path(_lowercase				)

																		self.closed_nodes.append(_lowercase				)
																		_lowerCAmelCase  						=			self.get_successors(_lowercase				)

																		for child_node in successors:
																								if child_node in self.closed_nodes:
																														continue

																								if child_node not in self.open_nodes:
																														self.open_nodes.append(_lowercase				)
																								else:
																														# retrieve the best current path
																														_lowerCAmelCase  						=			self.open_nodes.pop(self.open_nodes.index(_lowercase				)				)

																														if child_node.g_cost < better_node.g_cost:
																																				self.open_nodes.append(_lowercase				)
																														else:
																																				self.open_nodes.append(_lowercase				)

												if not self.reached:
																		return [self.start.pos]
												return None




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			[]
												for action in delta:
																		_lowerCAmelCase  						=			parent.pos_x + action[1]
																		_lowerCAmelCase  						=			parent.pos_y + action[0]

																		if not (0 <= pos_x <= len(grid[0]				) - 1 and 0 <= pos_y <= len(_lowercase				) - 1):
																								continue

																		if grid[pos_y][pos_x] != 0:
																								continue

																		successors.append(
																		    Node(
																		        _lowercase   ,       _lowercase   ,       self.target.pos_y   ,       self.target.pos_x   ,       parent.g_cost + 1   ,       _lowercase   ,       )				)
												return successors




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			node
												_lowerCAmelCase  						=			[]
												while current_node is not None:
																		path.append((current_node.pos_y, current_node.pos_x)				)
																		_lowerCAmelCase  						=			current_node.parent
												path.reverse()
												return path


if __name__ == "__main__":
						_lowercase    =		(0, 0)
						_lowercase    =		(len(grid) - 1, len(grid[0]) - 1)
						for elem in grid:
												print(elem)

						print("""------""")

						_lowercase    =		GreedyBestFirst(init, goal)
						_lowercase    =		greedy_bf.search()
						if path:
												for pos_x, pos_y in path:
																		_lowercase    =		2

												for elem in grid:
																		print(elem)


'''simple docstring'''



import os


def A				():
						with open(os.path.dirname(__lowerCamelCase		) + """/grid.txt"""		) as f:
												_lowerCAmelCase  						=			[]  # noqa: E741
												for _ in range(20		):
																		l.append([int(__lowerCamelCase		) for x in f.readline().split()]		)

												_lowerCAmelCase  						=			0

												# right
												for i in range(20		):
																		for j in range(17		):
																								_lowerCAmelCase  						=			l[i][j] * l[i][j + 1] * l[i][j + 2] * l[i][j + 3]
																								if temp > maximum:
																														_lowerCAmelCase  						=			temp

        # down
												for i in range(17		):
																		for j in range(20		):
																								_lowerCAmelCase  						=			l[i][j] * l[i + 1][j] * l[i + 2][j] * l[i + 3][j]
																								if temp > maximum:
																														_lowerCAmelCase  						=			temp

        # diagonal 1
												for i in range(17		):
																		for j in range(17		):
																								_lowerCAmelCase  						=			l[i][j] * l[i + 1][j + 1] * l[i + 2][j + 2] * l[i + 3][j + 3]
																								if temp > maximum:
																														_lowerCAmelCase  						=			temp

        # diagonal 2
												for i in range(17		):
																		for j in range(3			,     20		):
																								_lowerCAmelCase  						=			l[i][j] * l[i + 1][j - 1] * l[i + 2][j - 2] * l[i + 3][j - 3]
																								if temp > maximum:
																														_lowerCAmelCase  						=			temp
												return maximum


if __name__ == "__main__":
						print(solution())
