Contiguous Repeated String

Time limit2sMemory limit512 MB

Summary

Given string S and k, choose k appended characters so that the resulting string has the longest substring of the form TT (a block repeated twice back to back), and report that length.

Level: Medium7 of 10
Topics: String, Brute force, String matching, Implementation
Solved: No attempts yet

Problem

A contiguous repeated string is a string in which the same string appears consecutively. "abcabc" is a contiguous repeated string because "abc" appears consecutively, "dd" because "d" appears consecutively, and "qwertyqwerty" because "qwerty" appears consecutively.

Given a string S, find the longest substring, among substrings of strings that can be made by appending k characters to the end of S, that is a contiguous repeated string.

Input

The first line contains the string S, and the second line contains k (1 ≤ k ≤ 200). The string consists only of lowercase English letters, and its length is at most 200.

Output

On the first line, print the length of the longest substring, among substrings of strings that can be made by appending k characters to the end of S, that is a contiguous repeated string.

Examples3

Example 1
Input
```
aaba
2
```
Expected output
```
6
```
Example 2
Input
```
aaabbbb
2
```
Expected output
```
6
```
Example 3
Input
```
abracadabra
10
```
Expected output
```
20
```