Given three integers M, N and K. Consider a grid of M * N, where mat[i][j] = i * j (1 based index). The task is to return the K^{th} smallest element in the M * N multiplication table.

Example 1:
Input:
M = 3, N = 3
K = 5
Output: 3
Explanation:
The 5^{th} smallest element is 3.
Example 2:
Input:
M = 2, N = 3
K = 6
Output: 6

Your Task:
You don't need to read input or print anything. Your task is to complete the function KthSmallest() which takes three integers as input and returns an integer as output.
Expected Time Complexity: O(M * log(M * N))
Expected Auxiliary Space: O(1)

Constraints:
1 <= M, N <= 3 * 10^{4}
1 <= K <= M * N

见题面

见题面