大学生程序设计邀请赛(华东师范大学)

B. 分词

单点时限: 2.0 sec

内存限制: 256 MB

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

其中 就是上面所提到的频率。 指的是单词的长度。

特别的,对于字典中没有出现过的词,

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

输入格式

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

所有单词长度之和不超过 ,最长单词长度不超过

接下来一行一个整数 ,表示有 个查询。

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

词典数据来源于 Wikipedia Project Gutenberg(可能需要代理),其中 1-10000 词汇。

查询数据来源于 IELTS Test。

输出格式

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

第一行是一个实数,表示最大能达到的收益。输出和答案相差不超过 即可认为正确。

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

  • 把这些单词依次串联起来可以得到原句子;
  • 所有单词的收益值相加得到第一行的实数。

样例

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

提示

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