421. k-th Product

Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Consider n integer numbers a1, a2,..., an. Consider the products of their m-tuples: b1, b2,..., bN. You are to find k-th largest product, i.e., k-th item in the list (bi) sorted in non-increasing 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, kCnm), followed by n integer numbers ai (-106ai ≤ 106).

Output
Output one integer number — the k-th 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.


Online Contester Team © 2002 - 2010. All rights reserved.