Naming the Computer

Time limit2sMemory limit512 MB

Summary

Given a string S and integer K, find the shortest string that contains S as a substring at least K times, and output its length.

Level: Hard8 of 10
Topics: String matching, Dynamic programming, String, Greedy
Solved: No attempts yet

Problem

Ukje is naming the computer he just bought.

The name of the new computer must contain $S$ , Ukje's favorite string, as a substring at least $K$ times. If several names are possible, the name must have the shortest length.

Given $S$ and $K$ , find the length of the name of Ukje's new computer.

Input

The first line gives $S$ and $K$ . $S$ consists only of lowercase English letters and has length at most 500,000. $K$ is a positive integer at most 1,000,000.

Output

Print the length of the name of Ukje's new computer on the first line.

Examples5

Example 1
Input
```
ada 3
```
Expected output
```
7
```
Example 2
Input
```
abc 2
```
Expected output
```
6
```
Example 3
Input
```
r 7
```
Expected output
```
7
```
Example 4
Input
```
rr 5
```
Expected output
```
6
```
Example 5
Input
```
abbababbbbababababba 2
```
Expected output
```
36
```