SGU 421 k-th Product

给定 $n$ 个整数 $a_1,a_2,\ldots,a_n$。对于每个大小为 $m$ 的下标集合，计算对应元素的乘积。不同的下标集合分别计数，即使它们对应的乘积相同。

将这 $\binom{n}{m}$ 个乘积按非递增顺序排列，求其中第 $k$ 个乘积。

输入格式

第一行包含三个整数 $n,m,k$，分别表示整数的个数、每次选择的整数个数以及所求乘积的名次。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示所有乘积中的第 $k$ 大值。

答案可能超出 $64$ 位整数的表示范围，请以十进制形式精确输出。

样例输入

4 3 3
2 3 3 5

样例输出

30

数据范围

• $1\le n\le 10^4$；
• $1\le m\le \min(13,n)$；
• $1\le k\le \min(10^4,\binom{n}{m})$；
• $-10^6\le a_i\le 10^6$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4 3 3
2 3 3 5

输出

30