Description

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

子弹字符串的分数是其所有后缀的分值之和。当子弹字符串为 “$b_1 b_2 \dots b_n$” 时，从其第 $k$ 个字符开始的后缀 $s_k$ （$1 \le k \le n$），即 “$b_k b_{k+1} \dots b_n$”，其分值是该后缀与目标字符串的最长公共前缀的长度。也就是说，如果目标字符串是 “$t_1 t_2 \dots t_m$”，那么当 $t_j = b_{k+j-1}$ 对于 $1 \le j \le p$ 成立，并且满足 $p = m$、$k + p - 1 = n$ 或 $t_{p+1} \ne b_{k+p}$ 时，$s_k$ 的分值就是 $p$。

你今天必须不惜一切代价赢得比赛，因为 Alyssa 承诺要和获胜者约会！比赛即将开始。赶快编写一个程序，对于给定的目标字符串和子弹长度，找出可达到的最高分数。

Input Format

输入包含两行，为一个测试用例。第一行包含一个非空的目标字符串，由最多 2000 个小写字母组成。第二行包含子弹字符串的长度，是一个不超过 2000 的正整数。

Output Format

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

ababc
6

10

aabaacaabaa
102

251

Hint

对于第一个样例，“ababab” 是最优的子弹字符串。它的六个后缀中，有三个后缀 “ababab”、“abab” 和 “ab” 分别获得了 $4$、$4$ 和 $2$ 分，总分为 $10$。子弹字符串 “ababca” 可能看起来不错，但其后缀 “ababca”、“abca” 和 “a” 分别得到 $5$、$2$ 和 $1$ 分，总和仅为 $8$。