Junior Card Duel#4578
Two players are playing a card game. Initially, each player is dealt a certain number of cards (let these be n_1 and n_2, respectively). Each turn, both players simultaneously select and reveal one card from their remaining cards. The player with the weaker card discards it, while the player with the stronger card takes their card back into their hand. If the cards are of equal strength, both are discarded. The game continues until at least one player has no cards remaining.
If at the end of the game one player still has at least one card, that player receives point and the other player receives . If both players run out of cards simultaneously, each receives points.
There are different types of cards. The dominance relationship between card types may not be transitive and is specified by a matrix . Here, A_{ij} is if card defeats card , and otherwise.
Determine the maximum average score the first player can achieve, assuming the second player employs a uniform strategy (that is, at each turn they choose one of their remaining cards with equal probability).
Constraints
1 \leq n_1, n_2, N \leq 8
A_{ij} + A_{ji} = 1 for i \neq j
A_{ii} = 0
The first line contains the number .
The next lines each contain integers describing matrix .
The following line contains n_1 and then n_1 integers, each representing the type of a card held by the first player.
The final line, in the same format, describes the second player’s cards.
Print the value of the game for the first player with accuracy at least 10^{-8}.
Example 1