URI Online Judge | 2109

Spies's Duel

By XVII Maratona de Programação IME-USP, 2013 BR Brazil

Timelimit: 2

Alexey and Boris were both KGB agents that were living at Ecaterimburgo in the 70's. The city was so boring that they decided to make up a game using dice and escape from a tedious death. In this game, each agent starts with A and B life points respectively. Both Alexey and Boris have a number of possible attacks. They attack each other in turns. The attacks are described by an amount of dice. The damage caused by an attack is the sum of the values in the dice.

In order to play they have honest dice with numbers from 1 to 12. That way, if one die with L sides has been rolled it will show an integer value between 1 and L with the same probability and in a independent way of any other dice rolled.

The agents know all their own attacks and the oponent attacks. That way they have to decide how to attack in each turn in order to maximize their victory probability.

Your task is to find what is the probability of each agent's victory.


The input is composed by several instances and it ends with the end of the file (EOF).

The first line of each instance has four integers: VA, VB (1 ≤ VA, VB ≤ 300), NA and NB (1 ≤ NA, NB ≤ 10). Each one of the next NA lines describe an Alexey's attack, they start with an integer D (1 ≤ D ≤ 3) and followed by D other integers L1 , . . . , LD (1 ≤ Li ≤ 12), indicating that in this attack Alexey has rolled D dice with L1 , L2 , . . . , LD sides. The next NB lines describe Bori's attacks in the same way.


For each instance, print one line with one float number rounded to 3 decimal places, indicating the probability of Alexey's victory, knowing that he starts attacking.

Sample Input Sample Output

2 12 2 1

1 12

3 4 4 5

2 1 1

5 5 1 2

1 6

2 3 5

2 1 6