레지스탕스

레지스탕스는 소수의 저항군이 부패한 정부와 맞서는 보드게임이다. 저항군은 정부를 무너뜨리려고 임무를 이어서 수행하지만, 조직에는 이미 첩자가 숨어 있다. 임무에 나간 팀에 첩자가 한 명만 있어도 임무는 무너질 수 있으므로 팀은 신중하게 골라야 한다.

이 문제는 그 게임을 단순하게 바꾼 것이다. 플레이어는 N명이고 그중 S명이 무작위로 첩자가 된다. 첩자를 고르는 방법은 $\binom{N}{S}$가지이고 모두 나올 확률이 같다. 각 플레이어는 자신이 첩자인지는 알지만 다른 사람이 첩자인지는 모른다.

한 게임은 임무 5개로 이루어진다. 임무마다 정해진 수의 플레이어가 팀이 되고, 팀에 들어간 첩자는 각자 공정한 동전을 던져 임무를 방해할지 정한다. 즉 팀에 들어간 첩자 한 명이 방해할 확률은 정확히 $1/2$이고, 첩자들의 결정은 서로 독립이다. 임무가 끝나면 방해 횟수만 공개되고 누가 방해했는지는 공개되지 않는다.

이미 끝난 임무 M개의 기록이 주어진다. i번째 임무에는 플레이어 $C_i$명이 참여했고 방해가 $F_i$번 있었으며, 참여한 플레이어의 번호도 주어진다.

이제 다음 임무에 나갈 팀으로 서로 다른 플레이어 Q명을 고른다. 주어진 기록을 조건으로 할 때 팀에 첩자가 없을 조건부확률이 가장 큰 팀을 고르고, 그 확률을 출력한다.

입력은 게임 여러 개로 이루어진다. 게임은 100개 이하이다.

각 게임의 첫 줄에는 N, S, M, Q가 공백으로 구분되어 주어진다. 차례로 플레이어 수, 첩자 수, 이미 끝난 임무 수, 다음 임무에 고를 플레이어 수이다. ($2 \le N \le 15$, $1 \le S \le N - 1$, $1 \le M \le 4$, $1 \le Q \le N - S$)

둘째 줄에는 $C_1, \dots, C_M$이 공백으로 구분되어 주어진다. ($1 \le C_i \le N$)

셋째 줄에는 $F_1, \dots, F_M$이 공백으로 구분되어 주어진다. ($0 \le F_i \le \min(C_i, S)$)

이어지는 M개의 줄 가운데 i번째 줄에는 i번째 임무에 참여한 플레이어의 번호 $C_i$개가 공백으로 구분되어 주어진다. 번호는 1 이상 N 이하이고 한 줄 안에서 겹치지 않는다.

입력의 마지막 줄은 0 0 0 0이며 이 줄은 처리하지 않는다.

각 게임의 기록은 적어도 한 가지 첩자 배정으로 설명된다. 즉 주어진 방해 횟수가 나올 확률은 0보다 크다.

게임마다 첩자가 없을 확률이 최대가 되도록 Q명을 골랐을 때의 그 확률을 한 줄에 출력한다. 소수점 아래 다섯째 자리까지 정확히 출력한다. 입력은 $10^{-6}$ 이하의 오차가 반올림 결과를 바꾸지 않도록 만들어져 있다. 고른 팀의 구성원은 출력하지 않는다.

예제 입력의 첫 번째 게임에는 플레이어가 4명, 첩자가 2명이다. 끝난 임무는 하나이고 다음 임무에 2명을 골라야 한다. 그 임무에는 플레이어 1과 2가 참여했고 방해가 2번 있었으므로 두 사람이 첩자다. 플레이어 3과 4를 고르면 첩자가 없는 것이 확실하므로 확률은 1이다.

두 번째 게임은 같은 임무에서 방해가 한 번도 없었던 경우다. 첩자 쌍은 6가지다. 1과 2가 첩자이면서 둘 다 방해하지 않을 확률은 $\frac{1}{6} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{24}$이다. 1과 3이 첩자이면서 1이 방해하지 않을 확률은 $\frac{1}{6} \cdot \frac{1}{2} = \frac{1}{12}$이고, 임무에 나간 한 명과 나가지 않은 한 명이 첩자인 나머지 세 경우도 값이 같다. 3과 4가 첩자이면 임무에 첩자가 없어서 방해가 없을 확률이 1이므로 이 경우의 확률은 $\frac{1}{6}$이다. 방해가 없었다는 조건에서 3과 4가 첩자일 조건부확률은

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

이다. 그래서 다음 임무에 1과 2를 고르면 첩자가 없을 확률이 $4/13 \approx 0.30769$이고, 이 값이 최댓값이다.

세 번째 게임에서는 임무가 두 개이고 각각 방해가 한 번씩 있었다. 첫 임무에서 한 명, 두 번째 임무에서 한 명을 고르는 것이 최선이다. 예를 들어 1과 3을 고르면 된다. 두 사람이 첩자일 확률이 각각 $1/2$이므로 둘 다 첩자가 아닐 확률은 $1/4$이다.