
import functools






def      lowerCamelCase__       (       __lowerCAmelCase						:						list[int]					,							__lowerCAmelCase						:						list[int]       ):




			"""simple docstring"""


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

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

			if len(__lowerCAmelCase       ) == 0:
						return 0

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

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

			lowerCAmelCase_      			=			set(__lowerCAmelCase       )

			@functools.cache
			def dynamic_programming(__lowerCAmelCase						:						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()





def      lowerCamelCase__       (       __lowerCAmelCase						:						int       ):




			"""simple docstring"""


			if upper_limit < 0:
						raise ValueError("Limit for the Catalan sequence must be ≥ 0"       )

			lowerCAmelCase_      			=			[0] * (upper_limit + 1)

			# Base case: C(0) = C(1) = 1
			lowerCAmelCase_      			=			1
			if upper_limit > 0:
						lowerCAmelCase_      			=			1

			# Recurrence relation: C(i) = sum(C(j).C(i-j-1)), from j = 0 to i
			for i in range(2					,							upper_limit + 1       ):
						for j in range(__lowerCAmelCase       ):
									catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

			return catalan_list


if __name__ == "__main__":
			print("\n********* Catalan Numbers Using Dynamic Programming ************\n")
			print("\n*** Enter -1 at any time to quit ***")
			print("\nEnter the upper limit (≥ 0) for the Catalan number sequence: ", end="")
			try:
						while True:
									_A     =  int(input().strip())
									if N < 0:
												print("\n********* Goodbye!! ************")
												break
									else:
												print(f"""The Catalan numbers from 0 through {N} are:""")
												print(catalan_numbers(N))
												print("Try another upper limit for the sequence: ", end="")
			except (NameError, ValueError):
						print("\n********* Invalid input, goodbye! ************\n")

			import doctest

			doctest.testmod()



