Statement
정수 과 문자열 가 주어진다.
당신은 알파벳 소문자로만 이루어진 길이가 정확히 인 문자열 를 만들어야 한다.
각 에 대해 가 의 부분 문자열(substring)로 한 번 등장할 때마다 점을 얻는다. 같은 가 여러 위치에서 등장하면 등장한 횟수만큼 점수를 얻는다. 또한 서로 다른 에 대해 일 수 있으며, 이 경우 두 문자열은 따로 점수에 기여한다.
얻을 수 있는 점수의 최댓값을 구하여라.
부분 문자열(substring)의 정의
문자열 가 문자열 의 부분 문자열로 등장한다는 것은, 어떤 정수 이 존재하여 , 이고
를 만족한다는 뜻이다.
즉, 의 연속한 몇 개의 문자로 이루어진 문자열이 와 같으면 가 의 부분 문자열로 등장한다고 한다.
Input
입력은 다음과 같은 형식으로 주어진다.
Output
얻을 수 있는 점수의 최댓값을 출력한다.
Constraints
- 는 알파벳 소문자로만 이루어져 있다.
- 모든 입력값은 정수이거나 문자열이다.
Subtasks
Samples
Sample 1
Input
5 2
a
aa
Output
9
Sample 2
Input
6 3
ab
ba
aba
Output
7