Problem J
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.
Input
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
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 |
