class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # Make m >= n
        if m < n:
            m, n = n, m

        @cache
        def num_smaller_diag(x: int) -> int:
            y = min(x, n)
            target = x * y
            ans = 1 if x == y else 0
            for cy in range(1, y + 1):
                cx = target // cy
                if target % cy == 0:
                    cx -= 1
                cx = min(cx, m)

                ans += cx - cy + 1
                ans += min(cx, n) - cy

            return ans

        # def num_smaller_diag_slow(x: int) -> int:
        #     y = min(x, n)
        #     target = x * y
        #     ans = 0
        #     for cx in range(1, m + 1):
        #         for cy in range(1, n + 1):
        #             if cx * cy < target:
        #                 ans += 1
        #     return ans
        # for x in range(1, m + 1):
        #     if num_smaller_diag(x) != num_smaller_diag_slow(x):
        #         print(x, num_smaller_diag(x), num_smaller_diag_slow(x))

        b, e = 1, m + 1
        smaller_x = 1
        while b < e:
            tx = (b + e) // 2
            num_smaller = num_smaller_diag(tx)
            if num_smaller < k:
                smaller_x = tx
                b = tx + 1
            else:
                e = tx

        num_smaller = num_smaller_diag(smaller_x)
        smaller_target = smaller_x * min(smaller_x, n)
        next_target = (smaller_target + 1) * min(smaller_x + 1, n)
        if num_smaller + 1 == k:
            return smaller_target



        nums = []
        for y in range(1, min(smaller_x, n) + 1):
            min_x, max_x = (smaller_target + y - 1) // y, next_target // y
            if min_x > m:
                continue
            if next_target % y == 0:
                max_x -= 1
            min_x = max(min_x, y)
            max_x = min(max_x, m)
            for x in range(min_x, max_x + 1):
                nums.append(x * y)
                if x != y and x <= n:
                    nums.append(x * y)
        nums.sort()

        # test_nums = []
        # for x in range(1, m + 1):
        #     for y in range(1, n + 1):
        #         if smaller_target <= x * y < next_target:
        #             test_nums.append(x * y)
        # test_nums.sort()
        # print(nums == test_nums, smaller_target, next_target)
        # print(nums)
        # print(test_nums)
        # print()

        return nums[k - num_smaller - 1]