



'''simple docstring'''





import heapq as hq
import math
from collections.abc import Iterator






class __A     :



 '''simple docstring'''







 def __init__(self					,  A			)       ->	Union[str, Any]:


      """simple docstring"""



      _a           =    str(id_			)
      _a           =    None
      _a           =    None
      _a           =    []
      _a           =    {}  # {vertex:distance}



 def __lt__(self					,  A			)       ->	Dict:


      """simple docstring"""



      return self.key < other.key



 def __repr__(self			)       ->	Tuple:


      """simple docstring"""



      return self.id



 def    a__    (self					,  A			)       ->	int:


      """simple docstring"""



      self.neighbors.append(A			)



 def    a__    (self					,  A					,  A			)       ->	int:


      """simple docstring"""



      _a           =    weight





def lowerCAmelCase    (__A    ,      __A    ,      __A    ,      __A):



     """simple docstring"""



     graph[a - 1].add_neighbor(graph[b - 1])
     graph[b - 1].add_neighbor(graph[a - 1])
     # add the edges:
     graph[a - 1].add_edge(graph[b - 1]    ,      __A)
     graph[b - 1].add_edge(graph[a - 1]    ,      __A)




def lowerCAmelCase    (__A    ,      __A):



     """simple docstring"""



     _a           =    []
     for u in graph:
          _a           =    math.inf
          _a           =    None
     _a           =    0
     _a           =    graph[:]
     while q:
          _a           =    min(__A)
          q.remove(__A)
          for v in u.neighbors:
               if (v in q) and (u.edges[v.id] < v.key):
                    _a           =    u
                    _a           =    u.edges[v.id]
     for i in range(1    ,      len(__A)):
          a.append((int(graph[i].id) + 1, int(graph[i].pi.id) + 1))
     return a




def lowerCAmelCase    (__A    ,      __A):



     """simple docstring"""



     for u in graph:
          _a           =    math.inf
          _a           =    None
     _a           =    0

     _a           =    list(__A)
     hq.heapify(__A)

     while h:
          _a           =    hq.heappop(__A)
          for v in u.neighbors:
               if (v in h) and (u.edges[v.id] < v.key):
                    _a           =    u
                    _a           =    u.edges[v.id]
                    hq.heapify(__A)

     for i in range(1    ,      len(__A)):
          yield (int(graph[i].id) + 1, int(graph[i].pi.id) + 1)




def lowerCAmelCase    ():



     """simple docstring"""





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()

