529. K-th Smallest Number in Multiplication Table

Given the dimensions m and n of a multiplication table (where entry at row i, column j is i*j for 1 <= i <= m and 1 <= j <= n), return the k-th smallest value in the table. Use binary search on the value. Input: 'm, n, k'.

Input: 'm, n, k'.

Output: Integer — the k-th smallest table value.

Examples

Input: 3, 3, 5
Output: 3
Explanation: Sorted table values; 5th is 3.

Input: 2, 3, 6
Output: 6
Explanation: Largest entry.

Input: 1, 1, 1
Output: 1
Explanation: Single entry.

Constraints

• 1<=m,n<=3*10^4
• 1<=k<=m*n

Asked by