P14874 [ICPC 2020 Yokohama R] 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_1 b_2 \dots b_n$”, the point of its suffix $s_k$ starting with the $k$-th character ($1 \le k \le n$), “$b_k b_{k+1} \dots b_n$”, is the length of its longest common prefix with the target string. That is, with the target string “$t_1 t_2 \dots t_m$”, the point of $s_k$ is $p$ when $t_j = b_{k+j-1}$ for $1 \le j \le p$ and either $p = m$, $k + p - 1 = n$, or $t_{p+1} \ne 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$.