21936번 - Suffixes may Contain Prefixes 다국어

You are playing a game on character strings. At the start of a game, a string of lowercase letters, called the target string, is given. Each of the players submits one string of lowercase letters, called a bullet string, of the specified length. The winner is the one whose bullet string marks the highest score.

The score of a bullet string is the sum of the points of all of its suffixes. When the bullet string is “b₁b₂...b_n”, the point of its suffix s_k starting with the k-th character (1 ≤ k ≤ n), “b_kb_k+1...b_n”, is the length of its longest common prefix with the target string. That is, with the target string “t₁t₂...t_m”, the point of s_k is p when t_j = b_k+j−1 for 1 ≤ j ≤ p and either p = m, k + p − 1 = n, or t_p+1 ≠ b_k+p holds.

You have to win the game today by any means, as Alyssa promises to have a date with the winner! The game is starting soon. Write a program in a hurry that finds the highest achievable score for the given target string and the bullet length.

The input consists of a single test case with two lines. The first line contains the non-empty target string of at most 2000 lowercase letters. The second line contains the length of the bullet string, a positive integer not exceeding 2000.

Output the highest achievable score for the given target string and the given bullet length.

For the first sample, “ababab” is the best bullet string. Three among its six suffixes, “ababab”, “abab”, and “ab” obtain 4, 4, and 2 points, respectively, achieving the score 10. A bullet string “ababca” may look promising, but its suffixes “ababca”, “abca”, and “a” get 5, 2, and 1, summing up only to 8.