B. 分词 - 大学生程序设计邀请赛（华东师范大学）

仪表盘所有提交榜单

单点时限: 2.0 sec

内存限制: 256 MB

有一句句子因为粘贴的时候出现了一点问题空格全部丢失了。现在给一本字典，每个词都对应这个词出现的频率（每十亿）。根据这个频率，我们可以根据下面的公式算出这个词带来的收益 $P (w o r d)$ ：

$P (w o r d) = {l e n}^{2} (w o r d) \cdot \ln (f r e q u e n c y (w o r d))$

其中 $f r e q u e n c y$ 就是上面所提到的频率。 $l e n$ 指的是单词的长度。

特别的，对于字典中没有出现过的词， $P (w o r d) = 0$ 。

请对句子进行适当的分割，使得分割得到的所有词收益之和最大。同一个词可以重复出现，收益算作多次。

先给出一本词典，词典的第一行是词条数（词条数约为 $40 000$ ），下面每行分别是单词和对应出现频率，用空格隔开。单词中只会出现英文字母大小写，不会有多余的空格。每个单词只会出现一次。频率是一个正实数。

所有单词长度之和不超过 $3 \cdot 10^{5}$ ，最长单词长度不超过 $30$ 。

接下来一行一个整数 $T$ $(T \leq 10)$ ，表示有 $T$ 个查询。

下面 $T$ 行，每行一个句子，句子长度不超过 $5 000$ 。句子中保证只含有英文字母大小写。注意单词匹配时，不区分大小写。

词典数据来源于 Wikipedia Project Gutenberg（可能需要代理），其中 1-10000 词汇。

查询数据来源于 IELTS Test。

对于每组数据，输出两行。

第一行是一个实数，表示最大能达到的收益。输出和答案相差不超过 $10^{- 3}$ 即可认为正确。

第二行输出一连串单词，单词和单词之间用空格隔开。满足：

Input

5
ano 10
ther 30
another 10
an 300
other 20
1
another

Output

112.826670
another

Input

5
ano 10.0
ther 30.0
another 10.0
an 300.0
other 2000.0
1
another

Output

212.837691
an other

样例给出的词典与测试数据有所不同。

NaN

比赛状态发生变化，点 OK 刷新。

OK

大学生程序设计邀请赛（华东师范大学）