Optimal Score Strategy in Chase Festival

The legendary anime mobile game La Lumière: Scarlet Intense Flame is about to end its service in March. In its final event, the Chase Festival, players navigate a randomly generated multi‐level maze. As a devoted fan, player Little S wants to finish with a special score that exactly fills the gap between his current total and a big target score. The rules for each maze challenge are as follows:

Process. The maze has a maximum of N layers. The player always starts at layer 1 with an accumulated score of 0 and chooses the highest‐difficulty maze. For each layer i (1 ≤ i ≤ N):

1. Before challenging layer i, the player picks one of two strategies:

   • Conservative with probabilities p_i,0 (failure), p_i,1 (success with ordinary evaluation), and p_i,2 (success with high evaluation).
   • Aggressive with probabilities q_i,0, q_i,1, and q_i,2 respectively.

2. If the challenge is successful, the player gains s_i,1 points for an ordinary evaluation or s_i,2 points for a high evaluation. These points are not immediately added to the final maze score. However, if the current layer is not the last (i < N), after a successful challenge the player may decide to either exit the maze voluntarily (settling the current accumulated score) or continue to the next level. In the final layer (i = N), the game automatically exits after the challenge.

3. If the challenge fails at any layer, the maze is exited immediately. In this case, the reward from the current layer is lost and the points accumulated in the previous layers are penalized: the final score becomes \(\lfloor c \times (\text{accumulated score})\rfloor\).

The target is to achieve a final maze score exactly equal to some integer T with 1 ≤ T ≤ M. Little S can choose his strategy at each level and decide when to exit so as to maximize the probability of exactly matching the target score. Your task is to compute the maximum probability (over all target values in the range [1, M]) that this can be achieved assuming optimal play.

Notation. All formulas use standard LaTeX syntax. For example, N is the number of levels, the penalty is applied as \(\lfloor c \times (\text{score})\rfloor\), and the probabilities satisfy \(p_{i,0}+p_{i,1}+p_{i,2}=1\) and \(q_{i,0}+q_{i,1}+q_{i,2}=1\).

inputFormat

The input begins with a line containing two integers N and M, where N is the number of maze layers and M is the maximum value for the target score.

The second line contains a floating‐point number c, the penalty coefficient.

Then follow N lines. The i-th line contains eight numbers: p_i,0 p_i,1 p_i,2 q_i,0 q_i,1 q_i,2 s_i,1 s_i,2. Here, p and q are the probabilities for the two strategies at layer i (with their sums equal to 1), and s_i,1 and s_i,2 are the scores for an ordinary or high evaluation respectively.

outputFormat

Output a floating‐point number representing the maximum probability (with an absolute error of up to \(10^{-6}\)) of achieving a final score exactly equal to some target T (where \(1 \le T \le M\)) when following an optimal strategy.

sample

2 10
0.5
0.1 0.6 0.3 0.2 0.5 0.3 3 5
0.2 0.5 0.3 0.1 0.7 0.2 4 6

0.420000