






from bisect import bisect
from itertools import accumulate


def        __lowercase    (  UpperCAmelCase__		,					UpperCAmelCase__		,					UpperCAmelCase__		,					UpperCAmelCase__      ):

					"""simple docstring"""






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









from graphs.minimum_spanning_tree_kruskal import kruskal


def        __lowercase    (  ):

					"""simple docstring"""






					__lowerCAmelCase					=							9
					__lowerCAmelCase					=							[
					    [0, 1, 4],
					    [0, 7, 8],
					    [1, 2, 8],
					    [7, 8, 7],
					    [7, 6, 1],
					    [2, 8, 2],
					    [8, 6, 6],
					    [2, 3, 7],
					    [2, 5, 4],
					    [6, 5, 2],
					    [3, 5, 14],
					    [3, 4, 9],
					    [5, 4, 10],
					    [1, 7, 11],
					]

					__lowerCAmelCase					=							kruskal(UpperCAmelCase__		,					UpperCAmelCase__      )

					__lowerCAmelCase					=							[
					    [7, 6, 1],
					    [2, 8, 2],
					    [6, 5, 2],
					    [0, 1, 4],
					    [2, 5, 4],
					    [2, 3, 7],
					    [0, 7, 8],
					    [3, 4, 9],
					]

					assert sorted(UpperCAmelCase__      ) == sorted(UpperCAmelCase__      )






