Vincents Stuhl mit Pfeife

在电视问答节目《Monstermind》中，参赛者选择一个主题，然后在固定的时间内回答关于该主题的问题。参赛者每答对一题得一分。当时间耗尽时，参赛者必须保持沉默。

Teresa 钻研了一个非常冷门的主题，以至于她知道所有可能被问到的问题以及所有对应的答案。由于竞争激烈，她决定有时在主持人读完问题之前就给出答案。主持人从可能的问题池中均匀随机地抽取每一个问题，且每个问题可能会被多次问到。主持人读题的速度为每秒一个单词。

Teresa 可以在主持人读题的过程中打断——在两个单词之间，甚至在听到第一个单词之前——但不能在单词中间打断，那样会非常不礼貌。回答问题也需要一秒钟，且主持人会在回答结束后立即开始读下一个问题，除非 Teresa 再次打断。

她编写了一个程序来帮助她选择最佳的回答时机，现在只剩下一个问题留给你了。她期望能得多少分？

例如，在第一个样例测试中，答案在听到一个单词后就完全确定了，因此在听到该单词后回答是最优的，Teresa 在 4 秒内答对了 2 个问题。在第二个样例测试中，如果第一个单词是 What，那么等待问题结束花费的时间太长。因此 Teresa 说了 4 次 Now!，并期望答对 1/3 的问题。

输入格式

第一行包含两个整数 $t$ 和 $n$ ($1 \le t \le 100, 1 \le n \le 100\,000$)，分别表示问答的总时长和问题总数。接下来的 $n$ 行，每行包含一个问题（由空格分隔的单词列表，并以问号结尾）和一个答案（单个单词）。

每个单词是由 ASCII 值在 ‘!’ 和 ‘∼’ 之间的非空格字符组成的序列。只有问题的最后一个单词带有问号（‘?’）。你可以假设没有任何一个问题是另一个问题的前缀，且标点符号是单词的一部分。大小写不同的单词被视为不同的单词。

保证所有单词的总字符数不超过 $100\,000$。

输出格式

输出最优策略下的期望得分。答案在 $10^{-6}$ 的相对或绝对误差范围内均可被接受。

样例

输入格式 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

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

输出格式 2

1.3333333333