1211 - Mr. Y's investment plan

Time Limit: 5s Memory Limit: 128MB

Submissions: 150 Solved: 14
Description
As a very poor man, Mr. Y only has N dollars. Now he wants to arrange an investment plan, so that after M years, he will have as much money as possible. There are C investment products, and Mr. Y knows their maturity (in the next M years) and the annual appreciation they offer. Will you help Mr. Y arranging an investment plan to earn as much money as possible?
Input
In the first line, there is an integer number T (1 <= T <= 20) means T test cases. In the following lines, there are T test cases. In every test case, the first line are three integer numbers N (1 <= N <= 1000), M (1 <= M <= 100) and C (1 <= C <= 100). In the next C lines, every line has M real numbers. The jth number on the ith line Aij(0.000 <= <= 1.000) means the annual appreciation if you invest the ith product for j years, Aij is accurated to 0.001.
Output
In every test case, you should output a single line with Mr. Y's money after M years, please accurate to 0.001.
Sample Input
3
10 3 3
0.384 0.887 0.778
0.916 0.794 0.336
0.387 0.493 0.650
22 3 8
0.691 0.060 0.764
0.927 0.541 0.427
0.173 0.737 0.212
0.369 0.568 0.430
0.783 0.531 0.863
0.124 0.068 0.136
0.930 0.803 0.023
0.059 0.070 0.168
94 7 2
0.043 0.230 0.374 0.422 0.920 0.785 0.538
0.199 0.325 0.316 0.371 0.414 0.527 0.092
Sample Output
70.337
158.159
4305.918
Hint
In the third sample test case, Mr. Y can first buy product 1 for 5 years and then buy product 2 for 2 years, so he can earn the maximum money $4,305.918: 94.000*(1+0.920)5*(1+0.325)5=4305.918
Source