421. kth Product
Time limit per test: 0.75
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Consider
n integer numbers
a_{1},
a_{2},...,
a_{n}. Consider the products of their
mtuples:
b_{1},
b_{2},...,
b_{N}. You are to find
kth largest product, i.e.,
kth item in the list (
b_{i}) sorted in nonincreasing order (items of the list are numbered starting from 1).
Note that the numbers can be negative.
Input
The input file contains three integer numbers
n,
m,
k (1 ≤
n,
k ≤ 10000, 1 ≤
m ≤ 13,
k ≤
C_{n}^{m}), followed by
n integer numbers
a_{i} (10
^{6} ≤
a_{i} ≤ 10
^{6}).
Output
Output one integer number — the
kth largest product.
Example(s)
sample input

sample output

4 3 3
2 3 3 5

30

There are four possible products in the example: 3 · 3 · 5 = 45, 2 · 3 · 5 = 30 (involving the first 3), 2 · 3 · 5 = 30 (involving the second 3), 2 · 3 · 3 = 18.