#P11023. [2016杭电多校]Product Bo

    ID: 10165 传统题 6000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-最佳优先搜索状态编码一维前缀和组合数乘法递推奇偶性分析

[2016杭电多校]Product Bo

Product Bo

Problem Description

Given NN real numbers a1,a2,…,aNa_1,a_2,\ldots,a_N. Consider a subsequence of aa: 1≤s1<s2<…<sM≤N1 \leq s_1 < s_2 < \ldots < s_M \leq N. Define f(s)=∏i=1Masif(s) = \prod_{i=1}^{M} a_{s_i}. Your task is to figure out the KK-th largest value of f(s)f(s) among all the (NM)\binom{N}{M} subsequences of length MM (same values count multiple times). It is known to all that multiplication of big numbers is troublesome. Therefore, we represent numbers in this format: first, a character '+', '-' or '0', indicating positive, negative, or zero respectively. If it's nonzero, then there follows a space and an integer in [−109,+109][-10^9,+10^9], indicating the logarithm of the absolute value of this number to some fixed base which ≥1\geq 1.

Input

Multiple test cases. For each test case, the first line contains three integers N,M,KN,M,K. Then follows NN lines, the ii-th of which indicates aia_i in the format described above. The input ends with a line 0 0 00~0~0. It is guaranteed that $1 \leq M \leq N, ~ 1 \leq K \leq \binom{N}{M}, ~ N,K \leq 2 \times 10^5$.

Output

For each test case print the answer in the format described above.

Sample Input

3 2 2
+ 3
+ 7
- 2
3 2 2
+ -1
0
0
0 0 0

Sample Output

- 5
0

Author

绍兴一中

Source

2016 Multi-University Training Contest 3