4482. 字符串游戏

【题目背景】

弗兰茜和尼利在家没什么干，于是凯蒂给他们俩出了一个字符串游戏。弗兰茜和尼利研究了许久都没有搞明白，于是决定考考你。

【题目描述】

给定一个由小写字符构成的字符串 $s$ 和一个整数 $n$，你的目标是构造一个字符串 $t$，使得字符串 $t$ 的长度为 $n$。

定义构造出来的字符串 $t$ 的价值是 $t$ 的所有后缀与字符串 $s$ 的最长公共前缀的长度的和，而你就要求出所有可能的 $t$ 中价值最大的 $t$ 的价值。

【输入格式】

共两行，第一行一个字符串 $s$，第二行一个整数 $n$。

【输出格式】

一个整数，表示构造出的字符串的可能的最大价值。

【样例输入】

ababc
6

【样例输出】

10

【样例说明】

最优的 $t$ 是“ababab”，它的六个后缀“ababab”，“babab”，“abab”，“bab”，“ab”，“b”分别贡献了 4，0，4，0，2，0 的价值。

【数据规模与约定】

对于 20% 的数据，保证 $n\le5$。

对于另外 40% 的数据，保证 $n\le100$。

对于 100% 的数据，保证 $n\le 2000,|s|\le 2000$，保证 $s$ 只由小写字符构成。

大样例

P14874