


'''simple docstring'''



from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

_lowercase    :    Any			     =  TypeVar("""T""")
_lowercase    :    Optional[Any]			     =  TypeVar("""U""")






class  UpperCamelCase__(     Generic[T, U] ):




				def __init__(	self    :				Optional[int]   ,					lowerCAmelCase    :				List[str]   ,					lowerCAmelCase    :				List[str]   )->  Any:

										"""simple docstring"""




										UpperCAmelCase         =			key
										UpperCAmelCase         =			val
										UpperCAmelCase         =			None
										UpperCAmelCase         =			None





				def __repr__(	self    :				List[str]   )->  Tuple:

										"""simple docstring"""




										return (
										    F"""Node: key: {self.key}, val: {self.val}, """
										    F"""has next: {bool(self.next   )}, has prev: {bool(self.prev   )}"""
										)







class  UpperCamelCase__(     Generic[T, U] ):




				def __init__(	self    :				int   )->  Optional[Any]:

										"""simple docstring"""




										UpperCAmelCase         =			DoubleLinkedListNode(lowercase_   ,					lowercase_   )
										UpperCAmelCase         =			DoubleLinkedListNode(lowercase_   ,					lowercase_   )
										UpperCAmelCase         =			self.rear, self.head




				def __repr__(	self    :				Optional[Any]   )->  Optional[Any]:

										"""simple docstring"""




										UpperCAmelCase         =			["DoubleLinkedList"]
										UpperCAmelCase         =			self.head
										while node.next is not None:
																rep.append(str(lowercase_   )   )
																UpperCAmelCase         =			node.next
										rep.append(str(self.rear   )   )
										return ",\n    ".join(lowercase_   )




				def   a__(	self    :				Union[str, Any]   ,					lowerCAmelCase    :				Any   )->  Optional[Any]:

										"""simple docstring"""




										UpperCAmelCase         =			self.rear.prev

										# All nodes other than self.head are guaranteed to have non-None previous
										assert previous is not None

										UpperCAmelCase         =			node
										UpperCAmelCase         =			previous
										UpperCAmelCase         =			node
										UpperCAmelCase         =			self.rear





				def   a__(	self    :				Optional[int]   ,					lowerCAmelCase    :				Any   )->  List[Any]:

										"""simple docstring"""




										if node.prev is None or node.next is None:
																return None

										UpperCAmelCase         =			node.next
										UpperCAmelCase         =			node.prev
										UpperCAmelCase         =			None
										UpperCAmelCase         =			None
										return node







class  UpperCamelCase__(     Generic[T, U] ):
				__magic_name__       :   str							= {}




				def __init__(	self    :				Optional[Any]   ,					lowerCAmelCase    :				List[Any]   )->  Optional[Any]:

										"""simple docstring"""




										UpperCAmelCase         =			DoubleLinkedList()
										UpperCAmelCase         =			capacity
										UpperCAmelCase         =			0
										UpperCAmelCase         =			0
										UpperCAmelCase         =			0
										UpperCAmelCase         =			{}




				def __repr__(	self    :				List[str]   )->  int:

										"""simple docstring"""




										return (
										    F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
										    F"""capacity={self.capacity}, current size={self.num_keys})"""
										)




				def __contains__(	self    :				Union[str, Any]   ,					lowerCAmelCase    :				List[Any]   )->  Any:

										"""simple docstring"""




										return key in self.cache




				def   a__(	self    :				Tuple   ,					lowerCAmelCase    :				Optional[int]   )->  str:

										"""simple docstring"""




										if key in self.cache:
																self.hits += 1
																UpperCAmelCase         =			self.cache[key]
																UpperCAmelCase         =			self.list.remove(self.cache[key]   )
																assert node == value_node

																# node is guaranteed not None because it is in self.cache
																assert node is not None
																self.list.add(lowercase_   )
																return node.val
										self.miss += 1
										return None




				def   a__(	self    :				Tuple   ,					lowerCAmelCase    :				List[str]   ,					lowerCAmelCase    :				Optional[Any]   )->  Union[str, Any]:

										"""simple docstring"""




										if key not in self.cache:
																if self.num_keys >= self.capacity:
																						# delete first node (oldest) when over capacity
																						UpperCAmelCase         =			self.list.head.next

																						# guaranteed to have a non-None first node when num_keys > 0
																						# explain to type checker via assertions
																						assert first_node is not None
																						assert first_node.key is not None
																						assert (
																						    self.list.remove(lowercase_   ) is not None
																						)  # node guaranteed to be in list assert node.key is not None

																						del self.cache[first_node.key]
																						self.num_keys -= 1
																UpperCAmelCase         =			DoubleLinkedListNode(lowercase_   ,					lowercase_   )
																self.list.add(self.cache[key]   )
																self.num_keys += 1

										else:
																# bump node to the end of the list, update value
																UpperCAmelCase         =			self.list.remove(self.cache[key]   )
																assert node is not None  # node guaranteed to be in list
																UpperCAmelCase         =			value
																self.list.add(lowercase_   )





				@classmethod
				def   a__(	cls    :				Dict   ,					lowerCAmelCase    :				List[Any] = 128   )->  Optional[int]:

										"""simple docstring"""




										def cache_decorator_inner(lowerCAmelCase    :				Optional[int]   ) -> Callable[..., U]:
																def cache_decorator_wrapper(*lowerCAmelCase    :				Optional[int]   ) -> U:
																						if func not in cls.decorator_function_to_instance_map:
																												UpperCAmelCase         =			LRUCache(lowercase_   )

																						UpperCAmelCase         =			cls.decorator_function_to_instance_map[func].get(args[0]   )
																						if result is None:
																												UpperCAmelCase         =			func(*lowercase_   )
																												cls.decorator_function_to_instance_map[func].put(args[0]   ,					lowercase_   )
																						return result

																def cache_info() -> LRUCache[T, U]:
																						return cls.decorator_function_to_instance_map[func]

																setattr(lowercase_   ,					'''cache_info'''   ,					lowercase_   )  # noqa: B010

																return cache_decorator_wrapper

										return cache_decorator_inner


if __name__ == "__main__":
	import doctest

	doctest.testmod()





'''simple docstring'''



import functools


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




						'''simple docstring'''






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

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

						if len(A  ) == 0:
												return 0

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

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

						UpperCAmelCase         =			set(A  )

						@functools.cache
						def dynamic_programming(A     :    int  ) -> int:
												if index > 3_65:
																		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()





