你正在玩一个关于字符的游戏。游戏开始时，会给出一个由小写字母组成的字符串，称为目标字符串（target string）。每位玩家提交一个指定长度的、由小写字母组成的字符串，称为子弹字符串（bullet string）。得分最高的玩家获胜。

子弹字符串的得分是其所有后缀得分的总和。当子弹字符串为 “$b_1b_2 \dots b_n$” 时，其从第 $k$ 个字符开始的后缀 $s_k$（即 “$b_k b_{k+1} \dots b_n$”）的得分定义为该后缀与目标字符串的最长公共前缀的长度。也就是说，对于目标字符串 “$t_1t_2 \dots t_m$”，当 $t_j = b_{k+j-1}$ 对所有 $1 \le j \le p$ 成立，且满足 $p = m$、$k + p - 1 = n$ 或 $t_{p+1} \neq b_{k+p}$ 其中之一时，$s_k$ 的得分为 $p$。

你必须不惜一切代价赢得今天的比赛，因为 Alyssa 答应与获胜者约会！比赛即将开始。请尽快编写一个程序，计算出对于给定的目标字符串和子弹字符串长度，所能达到的最高得分。

输入格式

输入包含单组测试数据，共两行。第一行包含一个非空的目标字符串，长度不超过 2000 个小写字母。第二行包含子弹字符串的长度，为一个不超过 2000 的正整数。

输出格式

输出对于给定的目标字符串和子弹字符串长度，所能达到的最高得分。

样例

样例输入 1

ababc
6

样例输出 1

10

样例输入 2

aabaacaabaa
102

样例输出 2

251

说明

对于第一个样例，“ababab” 是最佳的子弹字符串。在其六个后缀中，“ababab”、“abab” 和 “ab” 分别获得 4、4 和 2 分，总得分为 10。子弹字符串 “ababca” 看起来很有希望，但其后缀 “ababca”、“abca” 和 “a” 分别获得 5、2 和 1 分，总得分仅为 8。