题目背景

小爱是一名工厂的调度员。在流水线上，会陆续运来 $n$ 个箱子，每个箱子都有一个型号，型号共有 $26$ 种，型号以大写的英文字母 A 到 Z 为编号。

小爱需要将这些箱子从流水线上装卸下来，分成 $k$ 条队列存放。摆放的规则如下：

1. 每个箱子可以摆放到任意一条队列上。
2. 队列可长可短，没有限定每个队列最少或最多摆放多少箱子，有些队列可以一直空着。
3. 箱子必须按照流水线上先来后到的顺序安放，先到的箱子必须放在队列的前面。

小爱注重的是队列的美观度。她希望同一条队列中相邻的箱子尽量是同一类型的，请问你能帮她寻找一个最美观的摆放方案么？

题目描述

给定一个字符序列 $a_1a_2\cdots a_n$，请将它分解成 $k$ 或小于 $k$ 个子序列，使得所有子序列的差异值之和最小。

一个序列的差异值定义为该序列中出现的，连续由单个字符构成的子串数量，例如序列 AAABAA＝AAA+B+AA，差异值为 $3$：

输入格式

第一行：两个整数表示 $n$ 和 $k$； 第二行：$n$ 个大写英文字母表示 $a_1a_2\cdots a_n$。

输出格式

单个整数：表示子序列的差异值总和的最小值。

6 2
ABCABC

4

样例解释 1

两条队列分别为AAB和BCC

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 15$，$1\leq k\leq 3$；
• 对于 $60\%$ 的数据，$1\leq n\leq 100$，$1\leq k\leq 4$；
• 对于 $100\%$ 的数据，$1\leq n\leq 150$，$1\leq k\leq 5$。