CF721B.Passwords

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Vanya is managed to enter his favourite site Codehorses. Vanya uses nn distinct passwords for sites at all, however he can't remember which one exactly he specified during Codehorses registration.

Vanya will enter passwords in order of non-decreasing their lengths, and he will enter passwords of same length in arbitrary order. Just when Vanya will have entered the correct password, he is immediately authorized on the site. Vanya will not enter any password twice.

Entering any passwords takes one second for Vanya. But if Vanya will enter wrong password kk times, then he is able to make the next try only 55 seconds after that. Vanya makes each try immediately, that is, at each moment when Vanya is able to enter password, he is doing that.

Determine how many seconds will Vanya need to enter Codehorses in the best case for him (if he spends minimum possible number of second) and in the worst case (if he spends maximum possible amount of seconds).

输入格式

The first line of the input contains two integers nn and kk ( 1<=n,k<=1001<=n,k<=100 ) — the number of Vanya's passwords and the number of failed tries, after which the access to the site is blocked for 55 seconds.

The next nn lines contains passwords, one per line — pairwise distinct non-empty strings consisting of latin letters and digits. Each password length does not exceed 100100 characters.

The last line of the input contains the Vanya's Codehorses password. It is guaranteed that the Vanya's Codehorses password is equal to some of his nn passwords.

输出格式

Print two integers — time (in seconds), Vanya needs to be authorized to Codehorses in the best case for him and in the worst case respectively.

输入输出样例

  • 输入#1

    5 2
    cba
    abc
    bb1
    abC
    ABC
    abc
    

    输出#1

    1 15
    
  • 输入#2

    4 100
    11
    22
    1
    2
    22
    

    输出#2

    3 4
    

说明/提示

Consider the first sample case. As soon as all passwords have the same length, Vanya can enter the right password at the first try as well as at the last try. If he enters it at the first try, he spends exactly 11 second. Thus in the best case the answer is 11 . If, at the other hand, he enters it at the last try, he enters another 44 passwords before. He spends 22 seconds to enter first 22 passwords, then he waits 55 seconds as soon as he made 22 wrong tries. Then he spends 22 more seconds to enter 22 wrong passwords, again waits 55 seconds and, finally, enters the correct password spending 11 more second. In summary in the worst case he is able to be authorized in 1515 seconds.

Consider the second sample case. There is no way of entering passwords and get the access to the site blocked. As soon as the required password has length of 22 , Vanya enters all passwords of length 11 anyway, spending 22 seconds for that. Then, in the best case, he immediately enters the correct password and the answer for the best case is 33 , but in the worst case he enters wrong password of length 22 and only then the right one, spending 44 seconds at all.

首页