← 返回题目列表

Codeforces · 448/D

D. 乘法表

中文机器翻译题面 查看原题

冠军 Bizon 不仅迷人,而且非常聪明。

当我们中的一些人在学习乘法表时,冠军 Bizon 以他自己的方式玩得很开心。 Bizon the Champion画了一个n×m乘法表,其中第i行和第j列交集的元素等于i·j(表的行和列从1开始编号)。然后又问他:表中第k大的数是哪个数?冠军比松总是立即正确回答。你能重复他的成功吗?

考虑给定的乘法表。如果你按非递减顺序写出表中所有n·m个数字,那么你写出的第k个数字称为第k大数字。

输入

单行包含整数 n、m 和 k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m)。

输出

打印 n × m 乘法表中的第 k 大数。

示例

输入 #1

2 2 2

输出 #1

2

输入 #2

2 3 4

输出 #2

3

输入 #3

1 10 5

输出 #3

5

注意

2 × 3 乘法表如下所示: