






"""simple docstring"""





from copy import deepcopy



class       __A		:

					def __init__(			self  :      Dict     ,		__snake_case  :      list[int] | None = None     ,		__snake_case  :      int | None = None					)			->							Optional[int]:







											if arr is None and size is not None:
																	__magic_name__:	Optional[int]							=       size
																	__magic_name__:	int							=       [0] * size
											elif arr is not None:
																	self.init(__snake_case					)
											else:
																	raise ValueError("""Either arr or size must be specified"""					)

					def   lowerCamelCase__   (			self  :      Any     ,		__snake_case  :      list[int]					)			->							List[str]:
											__magic_name__:	Dict							=       len(__snake_case					)
											__magic_name__:	Optional[Any]							=       deepcopy(__snake_case					)
											for i in range(1     ,		self.size					):
																	__magic_name__:	List[str]							=       self.next_(__snake_case					)
																	if j < self.size:
																							self.tree[j] += self.tree[i]

					def   lowerCamelCase__   (			self  :      int					)			->							int:
											__magic_name__:	Union[str, Any]							=       self.tree[:]
											for i in range(self.size - 1     ,		0     ,		-1					):
																	__magic_name__:	List[Any]							=       self.next_(__snake_case					)
																	if j < self.size:
																							arr[j] -= arr[i]
											return arr

					@staticmethod
					def   lowerCamelCase__   (			__snake_case  :      int					)			->							Optional[Any]:
											return index + (index & (-index))

					@staticmethod
					def   lowerCamelCase__   (			__snake_case  :      int					)			->							Tuple:
											return index - (index & (-index))

					def   lowerCamelCase__   (			self  :      int     ,		__snake_case  :      int     ,		__snake_case  :      int					)			->							List[Any]:







											if index == 0:
																	self.tree[0] += value
																	return
											while index < self.size:
																	self.tree[index] += value
																	__magic_name__:	Optional[int]							=       self.next_(__snake_case					)

					def   lowerCamelCase__   (			self  :      Union[str, Any]     ,		__snake_case  :      int     ,		__snake_case  :      int					)			->							Union[str, Any]:
											self.add(__snake_case     ,		value - self.get(__snake_case					)					)

					def   lowerCamelCase__   (			self  :      Dict     ,		__snake_case  :      int					)			->							int:







											if right == 0:
																	return 0
											__magic_name__:	int							=       self.tree[0]
											right -= 1  # make right inclusive
											while right > 0:
																	result += self.tree[right]
																	__magic_name__:	List[Any]							=       self.prev(__snake_case					)
											return result

					def   lowerCamelCase__   (			self  :      Optional[Any]     ,		__snake_case  :      int     ,		__snake_case  :      int					)			->							List[Any]:
											return self.prefix(__snake_case					) - self.prefix(__snake_case					)

					def   lowerCamelCase__   (			self  :      str     ,		__snake_case  :      int					)			->							int:
											return self.query(__snake_case     ,		index + 1					)






					def   lowerCamelCase__   (			self  :      Optional[int]     ,		__snake_case  :      int					)			->							Tuple:
											value -= self.tree[0]
											if value < 0:
																	return -1

											__magic_name__:	List[str]							=       1  # Largest power of 2 <= size
											while j * 2 < self.size:
																	j *= 2

											__magic_name__:	Dict							=       0

											while j > 0:
																	if i + j < self.size and self.tree[i + j] <= value:
																							value -= self.tree[i + j]
																							i += j
																	j //= 2
											return i


if __name__ == "__main__":
							import doctest

							doctest.testmod()









from bisect import bisect
from itertools import accumulate





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase       ) ->			Dict:
	a									=				sorted(zip(__lowerCamelCase				,     __lowerCamelCase       )				,     key=lambda __lowerCamelCase       : x[0] / x[1]				,     reverse=__lowerCamelCase       )
	a							,					a									=				[i[0] for i in r], [i[1] for i in r]
	a									=				list(accumulate(__lowerCamelCase       )       )
	a									=				bisect(__lowerCamelCase				,     __lowerCamelCase       )
	return (
	    0
	    if k == 0
	    else sum(vl[:k]       ) + (w - acc[k - 1]) * (vl[k]) / (wt[k])
	    if k != n
	    else sum(vl[:k]       )
	)


if __name__ == "__main__":
		import doctest

		doctest.testmod()

