

class SCREAMING_SNAKE_CASE	:






			"""simple docstring"""




			def __init__(     self			,					__UpperCamelCase			,					__UpperCamelCase				):

				"""simple docstring"""


				snake_case_   		=			name
				snake_case_   		=			val


			def __str__(     self				):

				"""simple docstring"""


				return f"""{self.__class__.__name__}({self.name}, {self.val})"""







			def __lt__(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				return self.val < other.val







class SCREAMING_SNAKE_CASE	:






			"""simple docstring"""




			def __init__(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				snake_case_   		=			{}
				snake_case_   		=			{}
				snake_case_   		=			self.build_heap(__UpperCamelCase				)


			def __getitem__(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				return self.get_value(__UpperCamelCase				)


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				return (idx - 1) // 2


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				return idx * 2 + 1


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				return idx * 2 + 2


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				return self.heap_dict[key]


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				snake_case_   		=			len(__UpperCamelCase				) - 1
				snake_case_   		=			self.get_parent_idx(__UpperCamelCase				)

				for idx, i in enumerate(__UpperCamelCase				):
					snake_case_   		=			idx
					snake_case_   		=			i.val

				for i in range(__UpperCamelCase			,					-1			,					-1				):
					self.sift_down(__UpperCamelCase			,					__UpperCamelCase				)
				return array


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase			,					__UpperCamelCase				):

				"""simple docstring"""


				while True:
					snake_case_   		=			self.get_left_child_idx(__UpperCamelCase				)  # noqa: E741
					snake_case_   		=			self.get_right_child_idx(__UpperCamelCase				)

					snake_case_   		=			idx
					if l < len(__UpperCamelCase				) and array[l] < array[idx]:
						snake_case_   		=			l
					if r < len(__UpperCamelCase				) and array[r] < array[smallest]:
						snake_case_   		=			r

					if smallest != idx:
						snake_case_		,							snake_case_   		=			array[smallest], array[idx]
						(
						    (
						    snake_case_
						)		,							(
						    snake_case_
						)		,							
						)   		=			(
						    self.idx_of_element[array[smallest]],
						    self.idx_of_element[array[idx]],
						)
						snake_case_   		=			smallest
					else:
						break


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				snake_case_   		=			self.get_parent_idx(__UpperCamelCase				)
				while p >= 0 and self.heap[p] > self.heap[idx]:
					snake_case_		,							snake_case_   		=			self.heap[idx], self.heap[p]
					snake_case_		,							snake_case_   		=			(
					    self.idx_of_element[self.heap[idx]],
					    self.idx_of_element[self.heap[p]],
					)
					snake_case_   		=			p
					snake_case_   		=			self.get_parent_idx(__UpperCamelCase				)


			def       __lowerCAmelCase			(     self				):

				"""simple docstring"""


				return self.heap[0]


			def       __lowerCAmelCase			(     self				):

				"""simple docstring"""


				snake_case_		,							snake_case_   		=			self.heap[-1], self.heap[0]
				snake_case_		,							snake_case_   		=			(
				    self.idx_of_element[self.heap[-1]],
				    self.idx_of_element[self.heap[0]],
				)

				snake_case_   		=			self.heap.pop()
				del self.idx_of_element[x]
				self.sift_down(0			,					self.heap				)
				return x


			def       __lowerCAmelCase			(     self			,					__UpperCamelCase				):

				"""simple docstring"""


				self.heap.append(__UpperCamelCase				)
				snake_case_   		=			len(self.heap				) - 1
				snake_case_   		=			node.val
				self.sift_up(len(self.heap				) - 1				)


			def       __lowerCAmelCase			(     self				):

				"""simple docstring"""


				return len(self.heap				) == 0







			def       __lowerCAmelCase			(     self			,					__UpperCamelCase			,					__UpperCamelCase				):

				"""simple docstring"""


				assert (
				    self.heap[self.idx_of_element[node]].val > new_value
				), "newValue must be less that current value"
				snake_case_   		=			new_value
				snake_case_   		=			new_value
				self.sift_up(self.idx_of_element[node]				)







A									=  Node('R', -1)
A									=  Node('B', 6)
A									=  Node('A', 3)
A									=  Node('X', 1)
A									=  Node('E', 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
A									=  MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print('Min Heap - before decrease key')
for i in my_min_heap.heap:
		print(i)

print('Min Heap - After decrease key of node [B -> -17]')
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
		print(i)

if __name__ == "__main__":
		import doctest

		doctest.testmod()



import functools





def a(lowercase__      ,			lowercase__						):





	'''simple docstring'''

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

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

	if len(lowercase__						) == 0:
		return 0

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

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

	snake_case_   		=			set(lowercase__						)

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