← 返回题目列表

Codeforces · 721/B

B. 密码

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

Vanya 成功进入了他最喜欢的网站 Codehorses。 Vanya 在网站上使用了 n 个不同的密码,但他不记得在 Codehorses 注册期间到底指定了哪一个密码。

Vanya将按长度不减的顺序输入密码,并且他将以任意顺序输入相同长度的密码。当 Vanya 输入正确的密码时,他会立即在网站上获得授权。 Vanya 不会输入任何密码两次。

Vanya 输入任何密码都需要一秒钟。但如果 Vanya 输入错误密码 k 次,那么他只能在 5 秒后进行下一次尝试。 Vanya 立即进行每次尝试,也就是说,在 Vanya 能够输入密码的每个时刻,他都在这样做。

确定 Vanya 在最好的情况下(如果他花费尽可能少的秒数)和最坏的情况(如果他花费尽可能多的秒数)需要多少秒进入 Codehorses。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 100) — Vanya 的密码数量和失败尝试次数,之后该网站的访问将被阻止 5 秒。

接下来的 n 行包含密码,每行一个 - 由拉丁字母和数字组成的成对不同的非空字符串。每个密码长度不超过100个字符。

输入的最后一行包含 Vanya 的 Codehorses 密码。保证 Vanya 的 Codehorses 密码等于他的 n 个密码中的一些。

输出

打印两个整数——时间(以秒为单位),Vanya 需要分别在最好的情况和最坏的情况下被授权给 Codehorses。

示例

输入 #1

5 2
cba
abc
bb1
abC
ABC
abc

输出 #1

1 15

输入 #2

4 100
11
22
1
2
22

输出 #2

3 4

注意

考虑第一个示例案例。一旦所有密码的长度相同,Vanya 就可以在第一次尝试和最后一次尝试时输入正确的密码。如果他在第一次尝试时输入,则只花费 1 秒。因此,在最好的情况下,答案是 1。另一方面,如果他在最后一次尝试时输入了该密码,那么他之前又输入了 4 个密码。他花了 2 秒的时间输入前 2 个密码,然后在输入 2 次错误后他就等待了 5 秒。然后他又花了 2 秒输入了 2 个错误的密码,再次等待 5 秒,最后又花了 1 秒输入了正确的密码。总而言之,最坏的情况下他能够在 15 秒内获得授权。

考虑第二个示例案例。无法输入密码并阻止对该网站的访问。一旦所需的密码长度为 2,Vanya 就会输入所有长度为 1 的密码,为此花费 2 秒。然后,在最好的情况下,他立即输入正确的密码,最好的情况下答案是 3,但在最坏的情况下,他输入长度为 2 的错误密码,然后才输入正确的密码,总共花费了 4 秒。