
from __future__ import annotations






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  list[int]   ,							__lowerCAmelCase  :  list[int]   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			if counter == 0 or capacity == 0:
						return 0

			# If weight of the nth item is more than Knapsack of capacity,
			#   then this item cannot be included in the optimal solution,
			# else return the maximum of two cases:
			#   (1) nth item included
			#   (2) not included
			if weights[counter - 1] > capacity:
						return knapsack(__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							counter - 1    )
			else:
						lowerCAmelCase_      =     capacity - weights[counter - 1]
						lowerCAmelCase_      =     values[counter - 1] + knapsack(
						    __lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							counter - 1    )
						lowerCAmelCase_      =     knapsack(__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							counter - 1    )
						return max(__lowerCAmelCase   ,							__lowerCAmelCase    )


if __name__ == "__main__":
			import doctest

			doctest.testmod()





class      _lowerCAmelCase :




				def __init__( self					)    ->				None:
							# numbermap keys are the number and its values are lists of indexes sorted
							# in ascending order
							lowerCAmelCase_      =     {}
							# indexmap keys are an index and it's values are the number at that index
							lowerCAmelCase_      =     {}




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				list[int]:
							if isinstance(_UpperCamelCase    ,    (range, str)					):
										lowerCAmelCase_      =     list(_UpperCamelCase					)
							elif not isinstance(_UpperCamelCase    ,    _UpperCamelCase					):
										raise TypeError(
										    "binary_search_delete() only accepts either a list, range or str"					)

							lowerCAmelCase_      =     0
							lowerCAmelCase_      =     len(_UpperCamelCase					) - 1

							while low <= high:
										lowerCAmelCase_      =     (low + high) // 2
										if array[mid] == item:
													array.pop(_UpperCamelCase					)
													return array
										elif array[mid] < item:
													lowerCAmelCase_      =     mid + 1
										else:
													lowerCAmelCase_      =     mid - 1
							raise ValueError(
							    "Either the item is not in the array or the array was unsorted"					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				list[int]:
							if isinstance(_UpperCamelCase    ,    (range, str)					):
										lowerCAmelCase_      =     list(_UpperCamelCase					)
							elif not isinstance(_UpperCamelCase    ,    _UpperCamelCase					):
										raise TypeError(
										    "binary_search_insert() only accepts either a list, range or str"					)

							lowerCAmelCase_      =     0
							lowerCAmelCase_      =     len(_UpperCamelCase					) - 1

							while low <= high:
										lowerCAmelCase_      =     (low + high) // 2
										if array[mid] == index:
													# If the item already exists in the array,
													# insert it after the existing item
													array.insert(mid + 1    ,    _UpperCamelCase					)
													return array
										elif array[mid] < index:
													lowerCAmelCase_      =     mid + 1
										else:
													lowerCAmelCase_      =     mid - 1

        # If the item doesn't exist in the array, insert it at the appropriate position
							array.insert(_UpperCamelCase    ,    _UpperCamelCase					)
							return array




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				None:
							# Remove previous index
							if index in self.indexmap:
										lowerCAmelCase_      =     self.indexmap[index]
										if len(self.numbermap[n]					) == 1:
													del self.numbermap[n]
										else:
													lowerCAmelCase_      =     self.binary_search_delete(self.numbermap[n]    ,    _UpperCamelCase					)

        # Set new index
							lowerCAmelCase_      =     number

							# Number not seen before or empty so insert number value
							if number not in self.numbermap:
										lowerCAmelCase_      =     [index]

							# Here we need to perform a binary search insertion in order to insert
							# The item in the correct place
							else:
										lowerCAmelCase_      =     self.binary_search_insert(
										    self.numbermap[number]    ,    _UpperCamelCase					)




				def 					__a						( self    ,    _UpperCamelCase					)    ->				int:
							return self.numbermap.get(_UpperCamelCase    ,    [-1]					)[0]


if __name__ == "__main__":
			import doctest

			doctest.testmod()



