#P3392. Pitcher Rotation

Pitcher Rotation

Description

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, Pij, denote the winning percentage of pitcher j against team i, and a list of g + 10 numbers, d1, d2, …, dg + 10, to represent the schedule of the team, where di denotes the opponent team and di = 0 denotes that there is no game at the ith 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.

Input

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 p11, p12, …, p1n, and the ith line is pi1, pi2, …, pin, where each pij is a two-digit number (for example, 92 represents 0.92). The next g + 10 lines describe the schedule of the season, d1, d2, …, dg + 10.

Output

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

Source

Kaohsiung 2006