Mydeimos

时空限制

$\text{2s} \qquad \text{512MB}$

题目背景

都说了是番外篇啦，就来些番外一点的吧

你偶然间来到了 $\text{Amphoreus}$，遇到了 $\text{Mydeimos}$ 正在创作字典，你决定帮帮他

题目描述

$\text{Mydeimos}$ 会说出一个长度为 $n$ 的字符串 $S$，包含 $\text{H}, \text{K}, \text{S}$ 三种字符

你需要将这段字符串划分成 $k$ 段，分别印成 $k$ 本字典

一本字典的售价是其中恰好等于 $\text{HKS}$ 的子序列的数量

$\text{Mydeimos}$ 非常亲民，所以他想知道 $k$ 本字典售价之和最小是多少

输入格式

第一行两个整数 $n, k$

第二行一个长度为 $n$ 的字符串 $S$

输出格式

一行一个整数，表示答案

样例

样例输入1

9 1
HHHKKKSSS

样例输出1

27

样例解释1

$3 \times 3 \times 3 = 27$

样例输入2

12 2
HKSHKSHKSHKS

样例输出2

5

样例解释2

$\color{red}\text{HKSHK}\color{blue}\text{SHKSHKS}$

数据范围

对于所有的数据，满足 $1 \le k \le n \le 2 \times 10^{5}$

详细部分分如下：