시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 52 19 19 65.517%

문제

욱제는 새로 산 컴퓨터에 이름을 붙이려고 한다.

새로 산 컴퓨터의 이름은 욱제가 가장 좋아하는 문자열인 S가 최소 K번 부분 문자열로 등장해야 한다. 가능한 이름이 여러가지면 길이가 가장 짧아야 한다.

S와 K가 주어졌을 때, 욱제가 새로 산 컴퓨터 이름의 길이를 구해보자.

입력

첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 욱제가 새로 산 컴퓨터 이름의 길이를 출력한다.

예제 입력 1

ada 3

예제 출력 1

7

adadada는 ada가 3번 부분 문자열로 등장하는 길이가 가장 짧은 문자열이다.

예제 입력 2

abc 2

예제 출력 2

6

예제 입력 3

r 7

예제 출력 3

7

예제 입력 4

rr 5

예제 출력 4

6

예제 입력 5

abbababbbbababababba 2

예제 출력 5

36

예제 입력 6

abcabcabca 3

예제 출력 6

16

출처