其实是套路题。但有段时间没写过闵可夫斯基和优化 $dp$ 了，记录一下。

先简单回顾一下闵可夫斯基和。点集 $P$ 与 点集 $Q$ 的闵可夫斯基和定义为：$P+Q=\{a+b|a\in P,b\in Q\}$ 。

对于两个凸包的闵可夫斯基和，有如下性质：

1. $P+Q$ 也为凸包。
2. $P+Q$ 的边集由 $P,Q$ 的边按极角排序后连接的结果。

因此对于大小为 $n$ 和 $m$ 的两个凸包，我们可以通过 $O(n+m)$ 的时间复杂度求出它们的闵可夫斯基和。

对于 $(\max,+)$ 卷积和 $(\min,+)$ 卷积，我们也可以通过类似的方式进行优化。

以 $(\max,+)$ 卷积为例，设 $c_i=\max_{j+k=i}\{a_j+b_k\}$。

如果 $(i,a_i)$ 与 $(i,b_i)$ 分别构成凸包，它们的闵可夫斯基和即为 $(i,c_i)$ ，那么可以通过如上方法快速求解数组 $c$ 。

如何使用闵可夫斯基和优化 $dp$ ？对于 $f_{i,j}=\max_{k<j}\{f_{i-1,k}+a_i\}$ 这类的 $dp$ ，其中 $i$ 这一维可能是形如 “选择 $i$ 个物品” 状物。我们可以退一步，将序列 $dp$ 改为区间 $dp$ ，然后用 $[l,mid]$ 和 $[mid+1,r]$ 的答案合并得到 $[l,r]$ 的答案。考虑分治，这样合并两段区间的贡献相当于做闵可夫斯基和的过程，总复杂度 $O(n\log n)$ 。

回到这一题，由于 $L$ 固定，我们可以对每个 $i$ 预先求出 $[i,i+L-1]$ 合并出 MO.. 的答案。设 $f_{i,j}$ 表示考虑前 $i$ 位作为 MO.. 的起点，恰好包含 $j$ 段 MO.. 的答案，那么转移形式与上式类似，只是要求前一个转移点与当前点相差至少 $L$ 。将 $dp$ 改为区间 $dp$ ，设 $f_{l,r,a1,a2,k}$ 表示考虑第 $l$ 到 $r$ 位作为 MO.. 的起点，最左、右端的点离左右端点的距离状态分别为 $a_1,a_2$ ，至少包含 $k$ 段 MO.. 的答案。其中，$a_1,a_2$ 为 $0/1/2$ 分别表示距离两段距离为 $0/1/\geq2$ 。合并连段时做类似矩阵乘法，对 $a_1,a_2$ 做卷积。时间复杂度 $O(nL^2\log n)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
	ll x=0; bool f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=0; ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48); ch=getchar();
	}
	return f?x:-x;
}
inline void write(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const ll N=300009;
const ll INF=1e18;
ll L,n,c[N],a[N];
ll g[10][10];
string s;
struct Node{
	vector<ll> f[3][3];
};
vector<ll> merge(vector<ll> a,vector<ll> b){
	for(ll i=a.size()-1;i>=2;i--) a[i]-=a[i-1];
	for(ll i=b.size()-1;i>=2;i--) b[i]-=b[i-1];
	vector<ll> c(a.size()+b.size()-1);
	c[0]=a[0]+b[0];
	merge(a.begin()+1,a.end(),b.begin()+1,b.end(),c.begin()+1);
	for(ll i=1;i<a.size()+b.size()-1;i++){
		c[i]+=c[i-1];
	}
	return c;
}
void add(vector<ll>&x,vector<ll> y){
	while(x.size()<y.size()) x.push_back(INF);
	for(ll i=0;i<y.size();i++) x[i]=min(x[i],y[i]);
}
Node solve(ll l,ll r){
	if(r-l+1<=2*L){
		Node res;
		for(ll x=0;x<L;x++){
			for(ll y=0;y<L;y++){
				memset(g,0x3f,sizeof(g));
				for(ll i=l+x;i<=r-y;i++){
					g[i-l+1][1]=a[i];
					if(i-L>=l){
						for(ll j=2;j<=r-l+1;j++){
							g[i-l+1][j]=min(g[i-l+1][j],g[i-l+1-L][j-1]+a[i]);
						}
					}
					for(ll j=1;j<=r-l+1;j++){
						g[i-l+1][j]=min(g[i-l+1][j],g[i-l][j]);
					}
				}
				vector<ll> cur; cur.push_back(0);
				for(ll i=1;i<=r-l+1;i++){
					ll mn=INF;
					for(ll j=l;j<=r;j++){
						mn=min(mn,g[j-l+1][i]);
					}
					if(mn>=INF) break;
					cur.push_back(mn);
				}
				res.f[x][y]=cur;
			}
		}
		return res;
	}
	ll mid=(l+r)/2;
	auto ls=solve(l,mid),rs=solve(mid+1,r);
	Node res;
	for(ll i=0;i<=L-1;i++){
		for(ll j=0;j<=L-1;j++){
			for(ll mid=0;mid<=L-1;mid++){
				add(res.f[i][j],merge(ls.f[i][mid],rs.f[L-1-mid][j]));
			}
		}
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>L>>n;
	cin>>s; s=" "+s;
	for(ll i=1;i<=n;i++){
		cin>>c[i];
	}
	for(ll i=1;i<=n-L+1;i++){
		if(s[i]!='M') a[i]=c[i];
		for(ll j=i+1;j<=i+L-1;j++){
			if(s[j]!='O') a[i]+=c[j];
		}
	}
	Node res=solve(1,n-L+1);
	for(ll i=1;i<=n/L;i++){
		cout<<res.f[0][0][i]<<"\n";
	}
	return 0;
}