题目内容

小塔有一串字符$s$，如果一个串中至少有$k$个子串与$s$相同，那么这个串就是$s$的好串。

例如，如果$s$是$"aa"，k=3$，那么$”aaabcaabc“$是好串。

现在小塔想知道，对于给定的$s和k$，$s$是最短好串多少。

输入描述

第一行输入一个长度不超过$10^3$，且只有小写 字符串$s$。

第二行输入一个整数$k$代表好串要求的子串 $2≤k≤1e9$

输出描述

在一行输出一个整数，代表$s$的最短

样例1

输入

abc
2

输出

6

说明 最短好串是abcabc

样例2

输入

aabcaa
2 

输出

10

最短好串是aabcaabcaa