






"""simple docstring"""





def   a    (     __UpperCAmelCase      :    Union[str, Any]      ,   __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    Tuple      ,   __UpperCAmelCase      :    List[Any]  )    ->							Dict:
						global f  # a global dp table for knapsack
						if f[i][j] < 0:
												if j < wt[i - 1]:
																		__magic_name__:	Dict							=       mf_knapsack(i - 1      ,   __UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase  )
												else:
																		__magic_name__:	List[str]							=       max(
																		    mf_knapsack(i - 1      ,   __UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase  )      ,   mf_knapsack(i - 1      ,   __UpperCAmelCase      ,   __UpperCAmelCase      ,   j - wt[i - 1]  ) + val[i - 1]      ,   )
												__magic_name__:	List[str]							=       val
						return f[i][j]



def   a    (     __UpperCAmelCase      :    Tuple      ,   __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    List[Any]      ,   __UpperCAmelCase      :    List[str]  )    ->							int:
						__magic_name__:	Optional[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_:
																								__magic_name__:	Union[str, Any]							=       max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]]      ,   dp[i - 1][w_]  )
																		else:
																								__magic_name__:	Optional[Any]							=       dp[i - 1][w_]

						return dp[n][w_], dp



def   a    (     __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    list      ,   __UpperCAmelCase      :    list  )    ->							str:
						if not (isinstance(__UpperCAmelCase      ,   (list, tuple)  ) and isinstance(__UpperCAmelCase      ,   (list, tuple)  )):
												raise ValueError(
												    """Both the weights and values vectors must be either lists or tuples"""  )

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

						__magic_name__,			__magic_name__:	str							=       knapsack(__UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase  )
						__magic_name__:	set							=       set()
						_construct_solution(__UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase  )

						return optimal_val, example_optional_set



def   a    (     __UpperCAmelCase      :    list      ,   __UpperCAmelCase      :    list      ,   __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    set  )    ->							Dict:
						# for the current item i at a maximum weight j to be part of an optimal subset,
						# the optimal value at (i, j) must be greater than the optimal value at (i-1, j).
						# where i - 1 means considering only the previous items at the given maximum weight
						if i > 0 and j > 0:
												if dp[i - 1][j] == dp[i][j]:
																		_construct_solution(__UpperCAmelCase      ,   __UpperCAmelCase      ,   i - 1      ,   __UpperCAmelCase      ,   __UpperCAmelCase  )
												else:
																		optimal_set.add(__UpperCAmelCase  )
																		_construct_solution(__UpperCAmelCase      ,   __UpperCAmelCase      ,   i - 1      ,   j - wt[i - 1]      ,   __UpperCAmelCase  )


if __name__ == "__main__":
							__lowerCamelCase							=  [3, 2, 4, 4]
							__lowerCamelCase							=  [4, 3, 2, 3]
							__lowerCamelCase							=  4
							__lowerCamelCase							=  6
							__lowerCamelCase							=  [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
							__lowerCamelCase		,					__lowerCamelCase							=  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
							__lowerCamelCase		,					__lowerCamelCase							=  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)





import os
def 							SCREAMING_SNAKE_CASE_	(					)			->						List[str]:
       with open(os.path.dirname(UpperCAmelCase_				) + '''/p022_names.txt'''				) as file:
              SCREAMING_SNAKE_CASE_							:				Any		=str(file.readlines()[0]				)
              SCREAMING_SNAKE_CASE_							:				List[Any]		=names.replace('''"'''			,							''''''				).split(''','''				)

       names.sort()

       SCREAMING_SNAKE_CASE_							:				Optional[int]		=0
       SCREAMING_SNAKE_CASE_							:				Optional[int]		=0

       for i, name in enumerate(UpperCAmelCase_				):
              for letter in name:
                     name_score += ord(UpperCAmelCase_				) - 6_4

              total_score += (i + 1) * name_score
              SCREAMING_SNAKE_CASE_							:				Any		=0
       return total_score


if __name__ == "__main__":
 print(solution())
