'''simple docstring'''




from __future__ import annotations

from random import random




class    a__				:






     def __init__(			self		:		List[str]  ,    a		:		int | None = None   ):





         """simple docstring"""



         __lowerCamelCase          =  value
         __lowerCamelCase          =  random()
         __lowerCamelCase          =  None
         __lowerCamelCase          =  None






     def __repr__(			self		:		Any   ):





         """simple docstring"""



         from pprint import pformat

         if self.left is None and self.right is None:
             return f"""'{self.value}: {self.prior:.5}'"""
         else:
             return pformat(
                 {f"""{self.value}: {self.prior:.5}""": (self.left, self.right)}  ,    indent=1   )






     def __str__(			self		:		Union[str, Any]   ):





         """simple docstring"""



         __lowerCamelCase          =  str(self.value   ) + ''' '''
         __lowerCamelCase          =  str(self.left or ''''''   )
         __lowerCamelCase          =  str(self.right or ''''''   )
         return value + left + right






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   tuple[Node | None, Node | None]:
    if root is None:  # None tree is split into 2 Nones
        return None, None
    elif root.value is None:
        return None, None
    else:
        if value < root.value:
            __lowerCamelCase     ,  __lowerCamelCase          =  split(root.left    ,  UpperCamelCase__    )
            return left, root
        else:
            __lowerCamelCase     ,  __lowerCamelCase          =  split(root.right    ,  UpperCamelCase__    )
            return root, right






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   Node | None:
    if (not left) or (not right):  # If one node is None, return the other
        return left or right
    elif left.prior < right.prior:
        __lowerCamelCase          =  merge(left.right    ,  UpperCamelCase__    )
        return left
    else:
        __lowerCamelCase          =  merge(UpperCamelCase__    ,  right.left    )
        return right






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   Node | None:
    __lowerCamelCase          =  Node(UpperCamelCase__    )
    __lowerCamelCase     ,  __lowerCamelCase          =  split(UpperCamelCase__    ,  UpperCamelCase__    )
    return merge(merge(UpperCamelCase__    ,  UpperCamelCase__    )    ,  UpperCamelCase__    )






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   Node | None:
    __lowerCamelCase     ,  __lowerCamelCase          =  split(UpperCamelCase__    ,  value - 1    )
    __lowerCamelCase     ,  __lowerCamelCase          =  split(UpperCamelCase__    ,  UpperCamelCase__    )
    return merge(UpperCamelCase__    ,  UpperCamelCase__    )






def __lowerCAmelCase			(							UpperCamelCase__    )     ->   None:
    if not root:  # None
        return
    else:
        inorder(root.left    )
        print(root.value    ,  end=''','''    )
        inorder(root.right    )






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   Node | None:
    for arg in args.split():
        if arg[0] == "+":
            __lowerCamelCase          =  insert(UpperCamelCase__    ,  int(arg[1:]    )    )

        elif arg[0] == "-":
            __lowerCamelCase          =  erase(UpperCamelCase__    ,  int(arg[1:]    )    )

        else:
            print('''Unknown command'''    )

    return root






def __lowerCAmelCase			(							)     ->   None:
    __lowerCamelCase          =  None
    print(
        '''enter numbers to create a tree, + value to add value into treap, '''
        '''- value to erase all nodes with value. \'q\' to quit. '''    )

    __lowerCamelCase          =  input()
    while args != "q":
        __lowerCamelCase          =  interact_treap(UpperCamelCase__    ,  UpperCamelCase__    )
        print(UpperCamelCase__    )
        __lowerCamelCase          =  input()

    print('''good by!'''    )


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()

'''simple docstring'''




from bisect import bisect
from itertools import accumulate






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )     ->   str:
    __lowerCamelCase          =  sorted(zip(UpperCamelCase__    ,  UpperCamelCase__    )    ,  key=lambda UpperCamelCase__    : x[0] / x[1]    ,  reverse=UpperCamelCase__    )
    __lowerCamelCase     ,  __lowerCamelCase          =  [i[0] for i in r], [i[1] for i in r]
    __lowerCamelCase          =  list(accumulate(UpperCamelCase__    )    )
    __lowerCamelCase          =  bisect(UpperCamelCase__    ,  UpperCamelCase__    )
    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()
