



"""simple docstring"""


def  lowercase	(      _SCREAMING_SNAKE_CASE   :						int					,     _SCREAMING_SNAKE_CASE   :						List[str]				):






				'''simple docstring'''



				print('''\nThe shortest path matrix using Floyd Warshall algorithm\n'''				)
				for i in range(_SCREAMING_SNAKE_CASE				):
								for j in range(_SCREAMING_SNAKE_CASE				):
												if dist[i][j] != float('''inf'''				):
																print(int(dist[i][j]				)					,     end='''\t'''				)
												else:
																print('''INF'''					,     end='''\t'''				)
								print()







def  lowercase	(      _SCREAMING_SNAKE_CASE   :						Optional[int]					,     _SCREAMING_SNAKE_CASE   :						Tuple				):






				'''simple docstring'''



				_UpperCAmelCase					=    [[float('''inf'''				) for _ in range(_SCREAMING_SNAKE_CASE				)] for _ in range(_SCREAMING_SNAKE_CASE				)]

				for i in range(_SCREAMING_SNAKE_CASE				):
								for j in range(_SCREAMING_SNAKE_CASE				):
												_UpperCAmelCase					=    graph[i][j]

												# check vertex k against all other vertices (i, j)
				for k in range(_SCREAMING_SNAKE_CASE				):
								# looping through rows of graph array
								for i in range(_SCREAMING_SNAKE_CASE				):
												# looping through columns of graph array
												for j in range(_SCREAMING_SNAKE_CASE				):
																if (
																    dist[i][k] != float('''inf'''				)
																    and dist[k][j] != float('''inf'''				)
																    and dist[i][k] + dist[k][j] < dist[i][j]
																):
																				_UpperCAmelCase					=    dist[i][k] + dist[k][j]

				_print_dist(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				)
				return dist, v


if __name__ == "__main__":
					__A   :							Union[str, Any]										=   int(input("Enter number of vertices: "))
					__A   :							Dict										=   int(input("Enter number of edges: "))

					__A   :							int										=   [[float("inf") for i in range(v)] for j in range(v)]

					for i in range(v):
										__A   :							List[Any]										=   0.0

										# src and dst are indices that must be within the array size graph[e][v]
										# failure to follow this will result in an error
					for i in range(e):
										print("\nEdge ", i + 1)
										__A   :							str										=   int(input("Enter source:"))
										__A   :							int										=   int(input("Enter destination:"))
										__A   :							List[str]										=   float(input("Enter weight:"))
										__A   :							Optional[Any]										=   weight

					floyd_warshall(graph, v)

					# Example Input
					# Enter number of vertices: 3
					# Enter number of edges: 2

					# # generated graph from vertex and edge inputs
					# [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
					# [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]

					# specify source, destination and weight for edge #1
					# Edge  1
					# Enter source:1
					# Enter destination:2
					# Enter weight:2

					# specify source, destination and weight for edge #2
					# Edge  2
					# Enter source:2
					# Enter destination:1
					# Enter weight:1

					# # Expected Output from the vertice, edge and src, dst, weight inputs!!
					# 0		INF	INF
					# INF	0	2
					# INF	1	0








"""simple docstring"""


import functools







def  lowercase	(      _SCREAMING_SNAKE_CASE   :						list[int]					,     _SCREAMING_SNAKE_CASE   :						list[int]				):






				'''simple docstring'''



				if not isinstance(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				) or not all(isinstance(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				) for day in days				):
								raise ValueError('''The parameter days should be a list of integers'''				)

				if len(_SCREAMING_SNAKE_CASE				) != 3 or not all(isinstance(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				) for cost in costs				):
								raise ValueError('''The parameter costs should be a list of three integers'''				)

				if len(_SCREAMING_SNAKE_CASE				) == 0:
								return 0

				if min(_SCREAMING_SNAKE_CASE				) <= 0:
								raise ValueError('''All days elements should be greater than 0'''				)

				if max(_SCREAMING_SNAKE_CASE				) >= 366:
								raise ValueError('''All days elements should be less than 366'''				)

				_UpperCAmelCase					=    set(_SCREAMING_SNAKE_CASE				)

				@functools.cache
				def dynamic_programming(_SCREAMING_SNAKE_CASE   :						int				) -> int:
								if index > 365:
												return 0

								if index not in days_set:
												return dynamic_programming(index + 1				)

								return min(
								    costs[0] + dynamic_programming(index + 1				)					,     costs[1] + dynamic_programming(index + 7				)					,     costs[2] + dynamic_programming(index + 30				)					,     )

				return dynamic_programming(1				)


if __name__ == "__main__":
					import doctest

					doctest.testmod()



