Just a Quiz

On a TV quiz show a contestant picks a topic and then gets questions about it for a fixed length of time. Each correct answer is worth one point. When the time runs out, the contestant has to stay silent.

Teresa found a topic narrow enough that she knows every question that can be asked and every answer to it. The competition is fierce, so she decided to answer some questions before the host finishes reading them. The host picks one of the $n$ questions uniformly at random every time, and the same question can come up more than once. The host reads one word per second.

Teresa can cut the host off between two words, and she can also cut in before the first word. She never cuts in the middle of a word, which would be very rude. Saying an answer also takes one second, and as soon as she is done the host starts reading the next question. She may of course cut that one off as well.

Compute the expected score Teresa gets when she plays optimally.

In the first sample the answer is settled after one word, so hearing one word and answering right away is optimal. Teresa gets two questions right in four seconds. In the second sample, if the first word is What, waiting for the question to end costs too much time. Teresa shouts Now! four times instead and expects to get one third of them right.

The first line contains the duration of the quiz $t$ and the number of questions $n$. ($1 \le t \le 100$, $1 \le n \le 100\,000$)

Each of the next $n$ lines holds one question and its answer. A line is a list of words separated by single spaces, where the last word is the answer and the words before it are the question. The last word of a question ends with a question mark, and no other word of a question contains one. The answer may contain a question mark.

Every word consists of characters with ASCII codes 33 (!) through 126 (~). Punctuation is part of a word, and two words that differ in case are different words. No question is a prefix of another question.

The total number of characters over all words is at most $100\,000$.

Print the expected score of an optimal strategy on one line, rounded to exactly 10 digits after the decimal point.