접미사는 접두사를 포함할 수 있다

문자열 게임을 한다. 게임이 시작할 때 소문자로 이루어진 문자열이 하나 주어지며, 이를 목표 문자열이라 한다. 각 참가자는 정해진 길이의 소문자 문자열을 하나 제출하며, 이를 총알 문자열이라 한다. 점수가 가장 높은 총알 문자열을 제출한 사람이 이긴다.

총알 문자열의 점수는 모든 접미사의 점수 합이다. 총알 문자열이 “b1b2...bn”일 때, k번째 문자에서 시작하는 접미사 sk(1 ≤ k ≤ n), 즉 “bkbk+1...bn”의 점수는 목표 문자열과의 최장 공통 접두사의 길이이다. 목표 문자열이 “t1t2...tm”일 때, 1 ≤ j ≤ p에 대해 tj = bk+j−1이고 p = m이거나 k + p − 1 = n이거나 tp+1 ≠ bk+p이면 sk의 점수는 p이다.

Alyssa가 우승자와 데이트를 약속했으므로, 오늘은 어떤 수를 써서든 게임에서 이겨야 한다. 게임이 곧 시작한다. 주어진 목표 문자열과 총알 길이에 대해 얻을 수 있는 최고 점수를 구하는 프로그램을 서둘러 작성하라.

입력은 두 줄로 이루어진 단일 테스트 케이스이다. 첫째 줄에는 길이가 2000 이하인 비어 있지 않은 소문자 목표 문자열이 주어진다. 둘째 줄에는 총알 문자열의 길이가 주어지며, 2000 이하인 양의 정수이다.

주어진 목표 문자열과 총알 길이에 대해 얻을 수 있는 최고 점수를 출력한다.

첫 번째 예제에서는 “ababab”이 가장 좋은 총알 문자열이다. 여섯 접미사 중 “ababab”, “abab”, “ab” 세 개가 각각 4, 4, 2점을 얻어 점수 10을 달성한다. 총알 문자열 “ababca”는 그럴듯해 보이지만, 접미사 “ababca”, “abca”, “a”가 각각 5, 2, 1점을 얻어 합이 8에 불과하다.