少女曾见的日本原风景
题号：NC252417
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

东风谷早苗想起了一道以前见过的ACM题，她打算做出这道题然后跟灵梦显摆。题目是这样的：

定义 w(s,t) 为有多少个不同的回文串同时在 s 和 t 中出现。定义字符串 s 的 val 函数为：
val(s) = \sum_{i=1}^{|s|-1} w^2(s_{1, i}, s_{i+1, |s|})
对于给定字符串 s，需要分割成 k 个子段，最大的子段的 val 值最小。

显然早苗不会，于是这道题是你的了。

输入描述:

第一行两个正整数，表示字符串长度 n 和字段数 k。
第二行一个字符串 s。

输出描述:

一个整数，表示分割后最小的 val 值。
示例1

输入

复制 
10 2
aabbaaabbb

输出

复制 
4

备注:

1 \leq k \leq n \leq 100000