

'''simple docstring'''







from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      bool:
       A_						       =   int(number**0.5					)
       return number == sq * sq
def    UpperCAmelCase__     (   UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)      ->      tuple[int, int]:
       A_						       =   x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
       A_						       =   x_den * y_den * z_den
       A_						       =   gcd(UpperCAmelCase__,							UpperCAmelCase__					)
       top //= hcf
       bottom //= hcf
       return top, bottom
def    UpperCAmelCase__     (   UpperCAmelCase__ = 35					)      ->      int:
       A_						       =   set()
       A_						       =   42
       A_						       =   Fraction(0					)
       A_						       =   42

       for x_num in range(1,							order + 1					):
              for x_den in range(x_num + 1,							order + 1					):
                     for y_num in range(1,							order + 1					):
                            for y_den in range(y_num + 1,							order + 1					):
                                   # n=1
                                   A_						       =   x_num * y_den + x_den * y_num
                                   A_						       =   x_den * y_den
                                   A_						       =   gcd(UpperCAmelCase__,							UpperCAmelCase__					)
                                   z_num //= hcf
                                   z_den //= hcf
                                   if 0 < z_num < z_den <= order:
                                          A_						       =   add_three(
                                              UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)
                                          unique_s.add(UpperCAmelCase__					)

                                   # n=2
                                   A_						       =   (
                                       x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
                                   )
                                   A_						       =   x_den * x_den * y_den * y_den
                                   if is_sq(UpperCAmelCase__					) and is_sq(UpperCAmelCase__					):
                                          A_						       =   int(sqrt(UpperCAmelCase__					)					)
                                          A_						       =   int(sqrt(UpperCAmelCase__					)					)
                                          A_						       =   gcd(UpperCAmelCase__,							UpperCAmelCase__					)
                                          z_num //= hcf
                                          z_den //= hcf
                                          if 0 < z_num < z_den <= order:
                                                 A_						       =   add_three(
                                                     UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)
                                                 unique_s.add(UpperCAmelCase__					)

                    # n=-1
                                   A_						       =   x_num * y_num
                                   A_						       =   x_den * y_num + x_num * y_den
                                   A_						       =   gcd(UpperCAmelCase__,							UpperCAmelCase__					)
                                   z_num //= hcf
                                   z_den //= hcf
                                   if 0 < z_num < z_den <= order:
                                          A_						       =   add_three(
                                              UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)
                                          unique_s.add(UpperCAmelCase__					)

                                   # n=2
                                   A_						       =   x_num * x_num * y_num * y_num
                                   A_						       =   (
                                       x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
                                   )
                                   if is_sq(UpperCAmelCase__					) and is_sq(UpperCAmelCase__					):
                                          A_						       =   int(sqrt(UpperCAmelCase__					)					)
                                          A_						       =   int(sqrt(UpperCAmelCase__					)					)
                                          A_						       =   gcd(UpperCAmelCase__,							UpperCAmelCase__					)
                                          z_num //= hcf
                                          z_den //= hcf
                                          if 0 < z_num < z_den <= order:
                                                 A_						       =   add_three(
                                                     UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)
                                                 unique_s.add(UpperCAmelCase__					)

       for num, den in unique_s:
              total += Fraction(UpperCAmelCase__,							UpperCAmelCase__					)

       return total.denominator + total.numerator


if __name__ == "__main__":
      print(f"""{solution() = }""")



'''simple docstring'''







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