Just a Quiz

In the TV quiz *Monstermind*, a contestant chooses a
topic and is then asked questions about it during a fixed
period of time. The contestant earns one point for each correct
answer. When the time runs out, the contestant must be
silent.

Teresa has figured out such a niche topic that she knows all possible questions that may be asked about it, as well as all the answers. Since the competition is fierce, she has decided to sometimes answer a question before the host finishes reading it. The host picks each question uniformly at random from the pool of possible questions, and each question may be asked multiple times. When reading a question, the host reads at a pace of one word per second.

Teresa can interrupt the host mid-question—between words, or even before hearing the first word—but not mid-word—that would be extremely impolite. Answering also takes one second, and the host will start reading another question immediately after an answer—unless Teresa interrupts again.

She wrote a program to help her choose the best moment to answer, and now there is only one question left for you. How many points does she expect to score?

For example, in the first sample test case the answer is
completely determined after hearing one word, so it is optimal
to answer after hearing it, and Teresa answers 2 questions
correctly in 4 seconds. In the second sample test case, if the
first word is `What`, then it takes too
much time to wait for the question to finish. Therefore Teresa
says `Now!` 4 times and expects to get
$1/3$ of the answers
right.

The first line contains two integers $t$ and $n$ ($1 \leq t \leq 100$, $1 \leq n \leq 100\ 000$), the duration of the quiz and the number of questions. Each of the following $n$ lines contains a question, which is a space-separated list of words terminated by a question mark; and an answer, which is a single word.

Each word is a sequence of non-space ASCII printable
characters, between the ASCII values of ‘`!`’ and ‘$\sim
$’. Only the last word of a question has a question mark
(‘`?`’). You can assume that no
question is a prefix of another and that punctuation marks are
part of a word. Words spelled with different upper/lower case
are assumed to be different.

It is guaranteed that the total number of word characters is at most $100\ 000$.

Output the expected score of an optimal strategy. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

Sample Input 1 | Sample Output 1 |
---|---|

4 4 How much is 6 times 9? 42 How much is 9 times 6? 42 Is there intelligent life on Earth? Probably What is the air speed velocity of an unladen swallow? African? |
2.0000000000 |

Sample Input 2 | Sample Output 2 |
---|---|

4 3 What do we send? Code What do we want? Accepted When do we want it? Now! |
1.333333333 |