def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   str:







    while b:
        __lowerCamelCase     ,  __lowerCamelCase          =  b, a % b
    return a






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    )     ->   Union[str, Any]:
    return a if b == 0 else euclidean_gcd_recursive(_lowercase    ,  a % b    )






def __lowerCAmelCase			(							)     ->   List[Any]:
    print(f"""euclidean_gcd(3, 5) = {euclidean_gcd(3    ,  5    )}"""    )
    print(f"""euclidean_gcd(5, 3) = {euclidean_gcd(5    ,  3    )}"""    )
    print(f"""euclidean_gcd(1, 3) = {euclidean_gcd(1    ,  3    )}"""    )
    print(f"""euclidean_gcd(3, 6) = {euclidean_gcd(3    ,  6    )}"""    )
    print(f"""euclidean_gcd(6, 3) = {euclidean_gcd(6    ,  3    )}"""    )

    print(f"""euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3    ,  5    )}"""    )
    print(f"""euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5    ,  3    )}"""    )
    print(f"""euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1    ,  3    )}"""    )
    print(f"""euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3    ,  6    )}"""    )
    print(f"""euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6    ,  3    )}"""    )


if __name__ == "__main__":
  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()
