





'''simple docstring'''

from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

__lowerCamelCase : str											=			TypeVar("T")







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return (position - 1) // 2







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return (2 * position) + 1







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return (2 * position) + 2

class       UpperCAmelCase (						Generic[T]  ):




		def __init__(self      :	List[str]				)					-> None:
						lowercase         = []
						lowercase         = {}
						lowercase         = 0




		def __len__(self      :	Tuple				)					-> int:
						return self.elements




		def __repr__(self      :	Optional[int]				)					-> str:
						return str(self.heap				)




		def 				UpperCAmelCase__   (self      :	Optional[Any]				)					-> bool:
						# Check if the priority queue is empty
						return self.elements == 0




		def 				UpperCAmelCase__   (self      :	str							,			A__      :	T							,			A__      :	int				)					-> None:
						# Add an element with given priority to the queue
						self.heap.append((elem, weight)				)
						lowercase         = self.elements
						self.elements += 1
						self._bubble_up(A__				)




		def 				UpperCAmelCase__   (self      :	Union[str, Any]				)					-> T:
						# Remove and return the element with lowest weight (highest priority)
						if self.elements > 1:
										self._swap_nodes(0							,			self.elements - 1				)
						lowercase   ,							lowercase         = self.heap.pop()
						del self.position_map[elem]
						self.elements -= 1
						if self.elements > 0:
										lowercase   ,							lowercase         = self.heap[0]
										self._bubble_down(A__				)
						return elem




		def 				UpperCAmelCase__   (self      :	Optional[int]							,			A__      :	T							,			A__      :	int				)					-> None:
						# Update the weight of the given key
						lowercase         = self.position_map[elem]
						lowercase         = (elem, weight)
						if position > 0:
										lowercase         = get_parent_position(A__				)
										lowercase   ,							lowercase         = self.heap[parent_position]
										if parent_weight > weight:
														self._bubble_up(A__				)
										else:
														self._bubble_down(A__				)
						else:
										self._bubble_down(A__				)




		def 				UpperCAmelCase__   (self      :	str							,			A__      :	T				)					-> None:
						# Place a node at the proper position (upward movement) [to be used internally
						# only]
						lowercase         = self.position_map[elem]
						if curr_pos == 0:
										return None
						lowercase         = get_parent_position(A__				)
						lowercase   ,							lowercase         = self.heap[curr_pos]
						lowercase   ,							lowercase         = self.heap[parent_position]
						if parent_weight > weight:
										self._swap_nodes(A__							,			A__				)
										return self._bubble_up(A__				)
						return None




		def 				UpperCAmelCase__   (self      :	Dict							,			A__      :	T				)					-> None:
						# Place a node at the proper position (downward movement) [to be used
						# internally only]
						lowercase         = self.position_map[elem]
						lowercase   ,							lowercase         = self.heap[curr_pos]
						lowercase         = get_child_left_position(A__				)
						lowercase         = get_child_right_position(A__				)
						if child_left_position < self.elements and child_right_position < self.elements:
										lowercase   ,							lowercase         = self.heap[child_left_position]
										lowercase   ,							lowercase         = self.heap[child_right_position]
										if child_right_weight < child_left_weight and child_right_weight < weight:
														self._swap_nodes(A__							,			A__				)
														return self._bubble_down(A__				)
						if child_left_position < self.elements:
										lowercase   ,							lowercase         = self.heap[child_left_position]
										if child_left_weight < weight:
														self._swap_nodes(A__							,			A__				)
														return self._bubble_down(A__				)
						else:
										return None
						if child_right_position < self.elements:
										lowercase   ,							lowercase         = self.heap[child_right_position]
										if child_right_weight < weight:
														self._swap_nodes(A__							,			A__				)
														return self._bubble_down(A__				)
						return None





		def 				UpperCAmelCase__   (self      :	Union[str, Any]							,			A__      :	int							,			A__      :	int				)					-> None:
						# Swap the nodes at the given positions
						lowercase         = self.heap[nodea_pos][0]
						lowercase         = self.heap[nodea_pos][0]
						lowercase   ,							lowercase         = (
						    self.heap[nodea_pos],
						    self.heap[nodea_pos],
						)
						lowercase         = nodea_pos
						lowercase         = nodea_pos




class       UpperCAmelCase (						Generic[T]  ):




		def __init__(self      :	List[Any]				)					-> None:
						lowercase         = {}
						lowercase         = 0




		def __repr__(self      :	Any				)					-> str:
						return str(self.connections				)




		def __len__(self      :	Dict				)					-> int:
						return self.nodes




		def 				UpperCAmelCase__   (self      :	Any							,			A__      :	T				)					-> None:
						# Add a node in the graph if it is not in the graph
						if node not in self.connections:
										lowercase         = {}
										self.nodes += 1





		def 				UpperCAmelCase__   (self      :	Dict							,			A__      :	T							,			A__      :	T							,			A__      :	int				)					-> None:
						# Add an edge between 2 nodes in the graph
						self.add_node(A__				)
						self.add_node(A__				)
						lowercase         = weight
						lowercase         = weight







def 							UpperCAmelCase_    (	lowerCAmelCase_		,							):

				"""simple docstring"""






				lowercase         = {node: maxsize for node in graph.connections}
				lowercase         = {node: None for node in graph.connections}

				lowercase         = MinPriorityQueue()
				for node, weight in dist.items():
								priority_queue.push(lowerCAmelCase_		,							lowerCAmelCase_							)

				if priority_queue.is_empty():
								return dist, parent

				# initialization
				lowercase         = priority_queue.extract_min()
				lowercase         = 0
				for neighbour in graph.connections[node]:
								if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
												lowercase         = dist[node] + graph.connections[node][neighbour]
												priority_queue.update_key(lowerCAmelCase_		,							dist[neighbour]							)
												lowercase         = node

    # running prim's algorithm
				while not priority_queue.is_empty():
								lowercase         = priority_queue.extract_min()
								for neighbour in graph.connections[node]:
												if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																lowercase         = dist[node] + graph.connections[node][neighbour]
																priority_queue.update_key(lowerCAmelCase_		,							dist[neighbour]							)
																lowercase         = node
				return dist, parent











'''simple docstring'''

import functools







def 							UpperCAmelCase_    (	lowerCAmelCase_		,							lowerCAmelCase_							):

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

				lowercase         = set(lowerCAmelCase_							)

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




