题目描述

在电视问答节目 Monstermind 中，选手选择一个主题，并在固定时间内回答相关问题。每答对一个问题得 $1$ 分。时间结束后，选手必须保持沉默。

Teresa 找到了一个非常冷门的主题，她知道这个主题下所有可能出现的问题以及它们的答案。主持人每次会从所有可能问题中等概率随机选择一个问题，而且同一个问题可以被问多次。主持人朗读问题的速度为每秒一个单词。

为了获得更高分，Teresa 可以在主持人读完问题之前抢答。她可以在两个单词之间，甚至在听到第一个单词之前打断主持人，但不能在一个单词中间打断。回答问题本身需要 $1$ 秒。回答结束后，主持人会立刻开始读下一道题，除非 Teresa 再次抢答。

如果 Teresa 抢答时，根据已经听到的前缀仍无法确定唯一答案，那么她需要选择一个答案，从而只有一定概率答对。

Teresa 写了一个程序来辅助选择最佳抢答时机。现在请你求出她在最优策略下的期望得分。

例如，第一个样例中，每道题听到第一个单词后答案就完全确定，因此最优策略是在听完一个单词后回答，$4$ 秒内能答对 $2$ 题。第二个样例中，如果第一个单词是 What，等待完整题目会花费太多时间；此时 Teresa 直接说 Now! 四次，期望答对 $1/3$ 的答案。

输入格式

第一行包含两个整数 $t,n$：

• $1 \le t \le 100$，表示问答总时长；
• $1 \le n \le 100000$，表示可能的问题数量。

接下来 $n$ 行，每行包含一个问题和一个答案。问题由若干空格分隔的单词组成，并以问号结尾；答案是一个单词。

每个单词由非空白的 ASCII 可打印字符组成，字符范围为 ! 到 ~。只有问题的最后一个单词包含问号 ?。保证没有一个问题是另一个问题的前缀，标点符号被视为单词的一部分，大小写不同的单词视为不同。

保证所有单词字符总数不超过 $100000$。

输出格式

输出最优策略下的期望得分。

答案允许绝对误差或相对误差不超过 $10^{-6}$。

输入输出样例 #1

输入 #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?

输出 #1

2.0000000000

输入输出样例 #2

输入 #2

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

输出 #2

1.333333333