

"""simple docstring"""






def   lowercase_	(    _lowercase       :		Optional[Any]							,      _lowercase       :		Union[str, Any]							,      _lowercase       :		Any							,      _lowercase       :		List[Any]	):




					'''simple docstring'''






					global f  # a global dp table for knapsack
					if f[i][j] < 0:
										if j < wt[i - 1]:
															UpperCAmelCase			:   str      =				mf_knapsack(i - 1							,      _snake_case							,      _snake_case							,      _snake_case	)
										else:
															UpperCAmelCase			:   str      =				max(
															    mf_knapsack(i - 1							,      _snake_case							,      _snake_case							,      _snake_case	)							,      mf_knapsack(i - 1							,      _snake_case							,      _snake_case							,      j - wt[i - 1]	) + val[i - 1]							,      )
										UpperCAmelCase			:   Union[str, Any]      =				val
					return f[i][j]



def   lowercase_	(    _lowercase       :		Dict							,      _lowercase       :		Optional[Any]							,      _lowercase       :		List[str]							,      _lowercase       :		List[Any]	):




					'''simple docstring'''






					UpperCAmelCase			:   List[Any]      =				[[0] * (w + 1) for _ in range(n + 1	)]

					for i in range(1							,      n + 1	):
										for w_ in range(1							,      w + 1	):
															if wt[i - 1] <= w_:
																				UpperCAmelCase			:   str      =				max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]]							,      dp[i - 1][w_]	)
															else:
																				UpperCAmelCase			:   str      =				dp[i - 1][w_]

					return dp[n][w_], dp



def   lowercase_	(    _lowercase       :		str							,      _lowercase       :		Optional[Any]							,      _lowercase       :		List[Any]	):




					'''simple docstring'''






					if not (isinstance(_snake_case							,      (list, tuple)	) and isinstance(_snake_case							,      (list, tuple)	)):
										raise ValueError(
										    "Both the weights and values vectors must be either lists or tuples"	)

					UpperCAmelCase			:   List[Any]      =				len(_snake_case	)
					if num_items != len(_snake_case	):
										UpperCAmelCase			:   List[Any]      =				(
										    "The number of weights must be the same as the number of values.\n"
										    F"""But got {num_items} weights and {len(_snake_case	)} values"""
										)
										raise ValueError(_snake_case	)
					for i in range(_snake_case	):
										if not isinstance(wt[i]							,      _snake_case	):
															UpperCAmelCase			:   Optional[Any]      =				(
															    "All weights must be integers but got weight of "
															    F"""type {type(wt[i]	)} at index {i}"""
															)
															raise TypeError(_snake_case	)

					UpperCAmelCase      ,							UpperCAmelCase			:   List[Any]      =				knapsack(_snake_case							,      _snake_case							,      _snake_case							,      _snake_case	)
					UpperCAmelCase			:   Dict      =				set()
					_construct_solution(_snake_case							,      _snake_case							,      _snake_case							,      _snake_case							,      _snake_case	)

					return optimal_val, example_optional_set



def   lowercase_	(    _lowercase       :		str							,      _lowercase       :		Dict							,      _lowercase       :		str							,      _lowercase       :		int							,      _lowercase       :		Any	):




					'''simple docstring'''






					if i > 0 and j > 0:
										if dp[i - 1][j] == dp[i][j]:
															_construct_solution(_snake_case							,      _snake_case							,      i - 1							,      _snake_case							,      _snake_case	)
										else:
															optimal_set.add(_snake_case	)
															_construct_solution(_snake_case							,      _snake_case							,      i - 1							,      j - wt[i - 1]							,      _snake_case	)


if __name__ == "__main__":
	snake_case_        =       [3, 2, 4, 4]
	snake_case_        =       [4, 3, 2, 3]
	snake_case_        =       4
	snake_case_        =       6
	snake_case_        =       [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
	snake_case_     ,      snake_case_        =       knapsack(w, wt, val, n)
	print(optimal_solution)
	print(mf_knapsack(n, wt, val, w))  # switched the n and w

	# testing the dynamic programming problem with example
	# the optimal subset for the above example are items 3 and 4
	snake_case_     ,      snake_case_        =       knapsack_with_example_solution(w, wt, val)
	assert optimal_solution == 8
	assert optimal_subset == {3, 4}
	print("""optimal_value = """, optimal_solution)
	print("""An optimal subset corresponding to the optimal value""", optimal_subset)





"""simple docstring"""






from functools import reduce

snake_case_   :   List[Any]        =       (
    """73167176531330624919225119674426574742355349194934"""
    """96983520312774506326239578318016984801869478851843"""
    """85861560789112949495459501737958331952853208805511"""
    """12540698747158523863050715693290963295227443043557"""
    """66896648950445244523161731856403098711121722383113"""
    """62229893423380308135336276614282806444486645238749"""
    """30358907296290491560440772390713810515859307960866"""
    """70172427121883998797908792274921901699720888093776"""
    """65727333001053367881220235421809751254540594752243"""
    """52584907711670556013604839586446706324415722155397"""
    """53697817977846174064955149290862569321978468622482"""
    """83972241375657056057490261407972968652414535100474"""
    """82166370484403199890008895243450658541227588666881"""
    """16427171479924442928230863465674813919123162824586"""
    """17866458359124566529476545682848912883142607690042"""
    """24219022671055626321111109370544217506941658960408"""
    """07198403850962455444362981230987879927244284909188"""
    """84580156166097919133875499200524063689912560717606"""
    """05886116467109405077541002256983155200055935729725"""
    """71636269561882670428252483600823257530420752963450"""
)



def   lowercase_	(    _lowercase       :		str = N	):




					'''simple docstring'''






					return max(
					    # mypy cannot properly interpret reduce
					    int(reduce(lambda _lowercase							,      _lowercase	: str(int(_lowercase	) * int(_lowercase	)	)							,      n[i : i + 13]	)	)
					    for i in range(len(_lowercase	) - 12	)	)


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


