P11459 [USACO24DEC] It's Mooin' Time P

**注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。** Bessie 有一个长度为 $N$（$1\le N\le 3\cdot 10^5$）的字符串，仅由字符 M 和 O 组成。对于字符串中的每个位置 $i$，需要花费 $c_i$ 来将该位置上的字符修改为另一种字符（$1\le c_i\le 10^8$）。 Bessie 认为，如果字符串包含更多长度为 $L$（$1\le L\le \min(N, 3)$）的哞叫会看起来更好。一个长度为 $L$ 的哞叫指的是一个 M 后面跟着 $L-1$ 个 O。 对于从 $1$ 到 $\lfloor N/L\rfloor$ 的每一个正整数 $k$，计算将字符串修改至包含至少 $k$ 个等于长度为 $L$ 的哞叫的子串的最小花费。

输入的第一行包含 $L$ 和 $N$。 下一行包含 Bessie 的长为 $N$ 的字符串，仅由字符 M 和 O 组成。 下一行包含空格分隔的整数 $c_1\dots c_N$。

输出 $\lfloor N/L\rfloor$ 行，依次包含每一个 $k$ 的答案。

- 测试点 $5$：$L=3, N\le 5000$。 - 测试点 $6$：$L=1$。 - 测试点 $7\sim 10$：$L=2$。 - 测试点 $11\sim 18$：$L=3$。