题目描述

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.

ababc
6

10

aabaacaabaa
102

251

提示

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$.