10261_PitcherRotation

For professional baseball team managers, it is an important task to decide the starting pitcher for each game. In the information era, massive data has been collected in professional sports. The manager knows the winning percentage of each pitcher against each team. Unfortunately, when playing against a certain team you cannot always pick the pitcher with the highest winning percentage against that team because there is a rule saying that after pitching a game the pitcher has to rest for at least four days. There are n pitchers (5 ≤ n ≤ 100), m opponent teams (3 ≤ m ≤ 30), and there are g (3 ≤ g ≤ 200) games in a season, and the season lasts for g + 10 days. Furthermore, there is at most one game per day. You are given an m by n matrix P, where an element in P, P_ij, denote the winning percentage of pitcher j against team i, and a list of g+10 numbers, d₁, d₂, …, d_g+10, to represent the schedule of the team, where d_i denotes the opponent team and d_i = 0 denotes that there is no game at the i^th day of the season. Your task is to decide the starting pitcher for each game so that the expected number of winning game is maximized.

The first line contains an integer t (1 ≤ t ≤ 5) indicating the number of teams that need your help. The data about these t teams follows. For each team, the first line contains the number of pitchers n, the number of opponent teams m, and the number of games in a season g. The next m lines contains the information about winning percentage of each pitcher against each team; the first line is p₁₁, p₁₂, …, p_1n, and the i^th line is p_i1, p_i2, …, p_in, where each p_ij is a two-digit number (for example, 92 represents 0.92). The next g+10 lines describe the schedule of the season,d₁, d₂, …, d_g+10.

The maximum value with exactly two digits past the decimal point of expected game won for these t teams in the order of their appearance in the input file, output the answer for each team in separated lines.

1
5 3 6
91 90 50 50 50
65 40 60 60 60
66 40 60 60 60
1
2
3
3
2
1
0
0
0
0
0
0
0
0
0
0

4.26