← 返回题目列表

Codeforces · 467/D

D. 费多尔和论文

中文机器翻译题面 查看原题

在你帮助Fedor在《士兵召唤3》游戏中找到朋友后,他完全停止了学习。今天,英语老师让他准备一篇论文。 Fedor 不想准备论文,所以他向 Alex 寻求帮助。亚历克斯来帮忙并为费多写了这篇文章。但费多尔根本不喜欢这篇文章。现在费多尔将使用英语同义词词典来修改这篇文章。

Fedor 不想改变这篇文章的含义。因此,他要做的唯一改变是:根据字典中的替换规则,将论文中的一个单词更改为其同义词之一。 Fedor 可以多次执行此操作。

因此,Fedor 希望得到一篇包含尽可能少的字母 «R»(大小写无关)的文章。如果有多篇文章的“R”数量最少,他希望获得长度最小的一篇(文章长度是其中所有单词的长度之和)。帮助费多获得所需的论文。

请注意,在这个问题中字母的大小写并不重要。例如,如果同义词词典规定单词cat可以用单词DOG替换,则允许用单词doG替换单词Cat。

输入

第一行包含一个整数 m (1 ≤ m ≤ 105) — 初始论文中的字数。第二行包含文章的文字。单词之间用一个空格分隔。保证单词总长度不超过105个字符。

下一行包含一个整数 n (0 ≤ n ≤ 105) — 同义词词典中单词对的数量。接下来 n 行的第 i 行包含两个空格分隔的非空单词 xi 和 yi。他们的意思是单词 xi 可以用单词 yi 代替(但反之则不然)。保证所有同义词对的总长度不超过5·105个字符。

输入的所有单词只能由英文字母的大小写字母组成。

输出

打印两个整数——最佳论文中字母“R”的最小数量和最佳论文的最小长度。

示例

输入 #1

3
AbRb r Zz
4
xR abRb
aA xr
zz Z
xr y

输出 #1

2 6

输入 #2

2
RuruRu fedya
1
ruruRU fedor

输出 #2

1 10