





import functools
from typing import Any







def       UpperCAmelCase							(     _lowerCamelCase      :  str			,   _lowerCamelCase      :  list[str]     ):





						'''simple docstring'''


						if not isinstance(_lowerCamelCase			,   _lowerCamelCase     ) or len(_lowerCamelCase     ) == 0:
												raise ValueError("the string should be not empty string"     )

						if not isinstance(_lowerCamelCase			,   _lowerCamelCase     ) or not all(
						    isinstance(_lowerCamelCase			,   _lowerCamelCase     ) and len(_lowerCamelCase     ) > 0 for item in words     ):
												raise ValueError("the words should be a list of non-empty strings"     )

						# Build trie
						SCREAMING_SNAKE_CASE__     :				dict[str, Any]   =					{}
						SCREAMING_SNAKE_CASE__     :				Union[str, Any]   =					"WORD_KEEPER"

						for word in words:
												SCREAMING_SNAKE_CASE__     :				Optional[Any]   =					trie
												for c in word:
																		if c not in trie_node:
																								SCREAMING_SNAKE_CASE__     :				Tuple   =					{}

																		SCREAMING_SNAKE_CASE__     :				str   =					trie_node[c]

												SCREAMING_SNAKE_CASE__     :				List[str]   =					True

						SCREAMING_SNAKE_CASE__     :				Union[str, Any]   =					len(_lowerCamelCase     )

						# Dynamic programming method
						@functools.cache
						def is_breakable(_lowerCamelCase      :  int     ) -> bool:
												if index == len_string:
																		return True

												SCREAMING_SNAKE_CASE__     :				Optional[int]   =					trie
												for i in range(_lowerCamelCase			,   _lowerCamelCase     ):
																		SCREAMING_SNAKE_CASE__     :				str   =					trie_node.get(string[i]			,   _lowerCamelCase     )

																		if trie_node is None:
																								return False

																		if trie_node.get(_lowerCamelCase			,   _lowerCamelCase     ) and is_breakable(i + 1     ):
																								return True

												return False

						return is_breakable(0     )


if __name__ == "__main__":
				import doctest

				doctest.testmod()






def       UpperCAmelCase							(     _lowerCamelCase      :  int = 1_000     ):





						'''simple docstring'''


						SCREAMING_SNAKE_CASE__     :				Dict   =					-1
						SCREAMING_SNAKE_CASE__     :				str   =					0
						for a in range(1			,   n // 3     ):
												# Solving the two equations a**2+b**2=c**2 and a+b+c=N eliminating c
												SCREAMING_SNAKE_CASE__     :				Tuple   =					(n * n - 2 * a * n) // (2 * n - 2 * a)
												SCREAMING_SNAKE_CASE__     :				Dict   =					n - a - b
												if c * c == (a * a + b * b):
																		SCREAMING_SNAKE_CASE__     :				str   =					a * b * c
																		if candidate >= product:
																								SCREAMING_SNAKE_CASE__     :				List[str]   =					candidate
						return product


if __name__ == "__main__":
				print(f"{solution() = }")