1211 - Mr. Y's investment plan:: HUST Online Judge

1211 - Mr. Y's investment plan

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 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 A_ij(0.000 <= <= 1.000) means the annual appreciation if you invest the ith product for j years, A_ij 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)⁵*(1+0.325)⁵=4305.918

source