


"""simple docstring"""






import math


class      __lowerCamelCase	:

     '''simple docstring'''


     def __init__(   self     ,					__UpperCAmelCase				)							->				Tuple:
          _a     						=					len(_SCREAMING_SNAKE_CASE				)
          _a     						=					[0] * (
              4 * self.N
          )  # approximate the overall size of segment tree with array N
          self.build(1     ,					0     ,					self.N - 1				)


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase				)							->				List[Any]:
          return idx * 2


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase				)							->				Union[str, Any]:
          return idx * 2 + 1


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase				)							->				List[Any]:  # noqa: E741
          if l == r:
               _a     						=					A[l]
          else:
               _a     						=					(l + r) // 2
               self.build(self.left(_SCREAMING_SNAKE_CASE				)     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)
               self.build(self.right(_SCREAMING_SNAKE_CASE				)     ,					mid + 1     ,					_SCREAMING_SNAKE_CASE				)
               _a     						=					max(self.st[self.left(_SCREAMING_SNAKE_CASE				)]     ,					self.st[self.right(_SCREAMING_SNAKE_CASE				)]				)


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase				)							->				int:
          return self.update_recursive(1     ,					0     ,					self.N - 1     ,					a - 1     ,					b - 1     ,					_SCREAMING_SNAKE_CASE				)


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase				)							->				Union[str, Any]:  # noqa: E741
          if r < a or l > b:
               return True
          if l == r:
               _a     						=					val
               return True
          _a     						=					(l + r) // 2
          self.update_recursive(self.left(_SCREAMING_SNAKE_CASE				)     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)
          self.update_recursive(self.right(_SCREAMING_SNAKE_CASE				)     ,					mid + 1     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)
          _a     						=					max(self.st[self.left(_SCREAMING_SNAKE_CASE				)]     ,					self.st[self.right(_SCREAMING_SNAKE_CASE				)]				)
          return True


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase     ,					__UpperCAmelCase				)							->				Tuple:
          return self.query_recursive(1     ,					0     ,					self.N - 1     ,					a - 1     ,					b - 1				)


     def 				_UpperCAmelCase   (   self     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase     ,					__UpperCAmelCase				)							->				str:  # noqa: E741
          if r < a or l > b:
               return -math.inf
          if l >= a and r <= b:
               return self.st[idx]
          _a     						=					(l + r) // 2
          _a     						=					self.query_recursive(self.left(_SCREAMING_SNAKE_CASE				)     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)
          _a     						=					self.query_recursive(self.right(_SCREAMING_SNAKE_CASE				)     ,					mid + 1     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)
          return max(_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)





     def 				_UpperCAmelCase   (   self				)							->				int:
          _a     						=					[]
          for i in range(1     ,					N + 1				):
               show_list += [self.query(_SCREAMING_SNAKE_CASE     ,					_SCREAMING_SNAKE_CASE				)]
          print(_SCREAMING_SNAKE_CASE				)


if __name__ == "__main__":
   __snake_case												=							[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
   __snake_case												=							15
   __snake_case												=							SegmentTree(A)
   print(segt.query(4, 6))
   print(segt.query(7, 11))
   print(segt.query(7, 12))
   segt.update(1, 3, 111)
   print(segt.query(1, 15))
   segt.update(7, 8, 235)
   segt.show_data()


from __future__ import annotations




def        __UpperCamelCase     (      _A					:							int      ,  _A					:							list[int]      ,  _A					:							list[int]      ,  _A					:							int		)				->int:



							"""simple docstring"""

							# Base Case
							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(_A      ,  _A      ,  _A      ,  counter - 1		)
							else:
														lowerCamelCase_								=capacity - weights[counter - 1]
														lowerCamelCase_								=values[counter - 1] + knapsack(
														    _A      ,  _A      ,  _A      ,  counter - 1		)
														lowerCamelCase_								=knapsack(_A      ,  _A      ,  _A      ,  counter - 1		)
														return max(_A      ,  _A		)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
