



"""simple docstring"""


from collections.abc import Sequence
from queue import Queue
class 			_a :
   """simple docstring"""



   def __init__(		self     :    List[Any]				,   __UpperCamelCase     :    List[str]				,   __UpperCamelCase     :    str				,   __UpperCamelCase     :    int				,   __UpperCamelCase     :    Tuple=None				,   __UpperCamelCase     :    Union[str, Any]=None   )->Any:
       _UpperCAmelCase					=    start
       _UpperCAmelCase					=    end
       _UpperCAmelCase					=    val
       _UpperCAmelCase					=    (start + end) // 2
       _UpperCAmelCase					=    left
       _UpperCAmelCase					=    right



   def __repr__(		self     :    Optional[Any]   )->Optional[int]:
       return F'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'



class 			_a :
   """simple docstring"""



   def __init__(		self     :    Optional[int]				,   __UpperCamelCase     :    Dict				,   __UpperCamelCase     :    List[Any]   )->List[str]:
       _UpperCAmelCase					=    collection
       _UpperCAmelCase					=    function
       if self.collection:
           _UpperCAmelCase					=    self._build_tree(0				,   len(_A   ) - 1   )



   def  lowercase__						(		self     :    int				,   __UpperCamelCase     :    Optional[Any]				,   __UpperCamelCase     :    Dict   )->str:
       self._update_tree(self.root				,   _A				,   _A   )



   def  lowercase__						(		self     :    Tuple				,   __UpperCamelCase     :    Optional[int]				,   __UpperCamelCase     :    Optional[Any]   )->Optional[Any]:
       return self._query_range(self.root				,   _A				,   _A   )



   def  lowercase__						(		self     :    Tuple				,   __UpperCamelCase     :    int				,   __UpperCamelCase     :    int   )->Optional[int]:
       if start == end:
           return SegmentTreeNode(_A				,   _A				,   self.collection[start]   )
       _UpperCAmelCase					=    (start + end) // 2
       _UpperCAmelCase					=    self._build_tree(_A				,   _A   )
       _UpperCAmelCase					=    self._build_tree(mid + 1				,   _A   )
       return SegmentTreeNode(_A				,   _A				,   self.fn(left.val				,   right.val   )				,   _A				,   _A   )



   def  lowercase__						(		self     :    Optional[Any]				,   __UpperCamelCase     :    Union[str, Any]				,   __UpperCamelCase     :    int				,   __UpperCamelCase     :    List[Any]   )->Dict:
       if node.start == i and node.end == i:
           _UpperCAmelCase					=    val
           return
       if i <= node.mid:
           self._update_tree(node.left				,   _A				,   _A   )
       else:
           self._update_tree(node.right				,   _A				,   _A   )
       _UpperCAmelCase					=    self.fn(node.left.val				,   node.right.val   )



   def  lowercase__						(		self     :    int				,   __UpperCamelCase     :    Optional[int]				,   __UpperCamelCase     :    Optional[int]				,   __UpperCamelCase     :    Optional[int]   )->str:
       if node.start == i and node.end == j:
           return node.val

       if i <= node.mid:
           if j <= node.mid:
               # range in left child tree
               return self._query_range(node.left				,   _A				,   _A   )
           else:
               # range in left child tree and right child tree
               return self.fn(
                   self._query_range(node.left				,   _A				,   node.mid   )				,   self._query_range(node.right				,   node.mid + 1				,   _A   )				,   )
       else:
           # range in right child tree
           return self._query_range(node.right				,   _A				,   _A   )



   def  lowercase__						(		self     :    int   )->Optional[int]:
       if self.root is not None:
           _UpperCAmelCase					=    Queue()
           queue.put(self.root   )
           while not queue.empty():
               _UpperCAmelCase					=    queue.get()
               yield node

               if node.left is not None:
                   queue.put(node.left   )

               if node.right is not None:
                   queue.put(node.right   )


if __name__ == "__main__":
     import operator

     for fn in [operator.add, max, min]:
          print("*" * 50)
          __A   :							Optional[Any]										=   SegmentTree([2, 1, 5, 3, 4], fn)
          for node in arr.traverse():
               print(node)
          print()

          arr.update(1, 5)
          for node in arr.traverse():
               print(node)
          print()

          print(arr.query_range(3, 4))  # 7
          print(arr.query_range(2, 2))  # 5
          print(arr.query_range(1, 3))  # 13
          print()








"""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()



