SP11613 AHOCUR - Aho-Corasick Trie

The **Aho–Corasick string matching algorithm** is a [string searching algorithm](http://en.wikipedia.org/wiki/String_searching_algorithm "String searching algorithm") invented by [Alfred V. Aho](http://en.wikipedia.org/wiki/Alfred_V._Aho "Alfred V. Aho") and [Margaret J. Corasick](http://en.wikipedia.org/wiki/Margaret_J._Corasick "Margaret J. Corasick"). It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all patterns simultaneously. The Algorithm described above, requires an input file generator. The generator generates a text of length _L_, by choosing _L_ characters randomly. Probability of choosing each character is given as priori, and independent of choosing others. Now, given a set of patterns, calculate the probability of a valid program generating “no”.

First line contains an integer _T_, the number of test cases. Each case starts with an integer _K_, the number of pattern strings. Next _K_ lines each contain a pattern string, followed by an integer _N_, number of valid characters. Next _N_ lines each contain a character and the probability of selecting that character, _p $ _{i} $_ . Next an integer _L_, the length of the string generated. The generated text can consist of only the valid characters, given above. There will be a blank line after each test case.

For each test case, output the number of test case, and the probability of getting a “no”. **Constraints** - T - K - Length of each pattern string is between 1 and 20 - Each pattern string consists of only alphanumeric characters (‘a’ to ‘z’, ‘A’ to ‘Z’,’0’ to ‘9’) - Valid characters are all alphanumeric characters - ∑p $ _{i } $ = 1 - L