The Resistance

The Resistance is a board game in which a small group of resistance fighters works against a corrupt government. The resistance keeps running missions to bring the government down, but spies have already infiltrated its ranks. A single spy on a mission team can bring the mission down, so the team has to be picked carefully.

This problem uses a simplified version of the game. There are N players and S of them become spies at random. There are $\binom{N}{S}$ ways to choose the spies and all of them are equally likely. A player knows whether they are a spy, but not who the other spies are.

A game consists of 5 missions. Each mission takes a fixed number of players as its team, and every spy on that team flips a fair coin to decide whether to sabotage the mission. A spy on the team sabotages with probability exactly $1/2$, and the spies decide independently of each other. When a mission ends, only the number of sabotages is revealed, never who caused them.

You are given the record of M missions that have already been played. Mission i had $C_i$ players and $F_i$ sabotages, and the ids of the players on that mission are given too.

You now pick a team of Q distinct players for the next mission. Given the record, pick the team with the largest conditional probability of holding no spy, and print that probability.

The input holds several games. There are at most 100 games.

The first line of each game has N, S, M, and Q separated by spaces: the number of players, the number of spies, the number of finished missions, and the number of players to pick for the next mission. ($2 \le N \le 15$, $1 \le S \le N - 1$, $1 \le M \le 4$, $1 \le Q \le N - S$)

The second line has $C_1, \dots, C_M$ separated by spaces. ($1 \le C_i \le N$)

The third line has $F_1, \dots, F_M$ separated by spaces. ($0 \le F_i \le \min(C_i, S)$)

Each of the next M lines describes one mission. Line i has the $C_i$ ids of the players on mission i, separated by spaces. Every id is between 1 and N, and no id repeats on one line.

The last line of the input is 0 0 0 0 and is not processed.

Every game record is explained by at least one assignment of spies, so the reported sabotage counts have positive probability.

For each game, print on one line the probability that the chosen team of Q players holds no spy, for the team that maximises this probability. Print the value with exactly 5 decimal places. The input is built so that an error of up to $10^{-6}$ does not change the rounded answer. Do not print the members of the team.

The first game of the example input has 4 players and 2 spies. One mission is finished and 2 players have to be picked for the next one. Players 1 and 2 were on that mission and there were 2 sabotages, so both of them are spies. Picking players 3 and 4 is certain to avoid the spies, so the probability is 1.

The second game is the same mission with no sabotages at all. There are 6 possible pairs of spies. The probability that 1 and 2 are the spies and neither sabotages is $\frac{1}{6} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{24}$. The probability that 1 and 3 are the spies and 1 does not sabotage is $\frac{1}{6} \cdot \frac{1}{2} = \frac{1}{12}$, and the same value holds for the other three cases with one spy on the mission and one spy off it. If 3 and 4 are the spies, the mission carries no spy, so no sabotage happens with probability 1 and this case has probability $\frac{1}{6}$. Conditioned on seeing no sabotage, the probability that 3 and 4 are the spies is

$\frac{1/6}{1/24 + 4 \cdot 1/12 + 1/6} = \frac{4}{13}$

so picking 1 and 2 for the next mission gives a spy free team with probability $4/13 \approx 0.30769$, which is the maximum.

The third game has two missions with one sabotage each. Taking one player from the first mission and one from the second is best, for example players 1 and 3. Each of them is a spy with probability $1/2$, so neither is a spy with probability $1/4$.