zhenglier @ 2018-09-05 08:48:01
#include<bits/stdc++.h>
#define re register int
#define lowbit(x) x&-x
#define max(a,b) (a>b?a:b)
using namespace std;
inline char read(){
char a;
for(a=getchar();a!='P' && a!='H';a=getchar());
return a;
}
int n,m;
int mp[110];
int f[110][1100][1100],k,zh[1100],sum[1100];
int main()
{
cin>>n>>m;
for(re i=1;i<=n;++i){
for(re j=0;j<m;++j){
mp[i]=mp[i]*2+((read()=='H'));
}
}
for(re i=0;i<(1<<m);++i){
if((!(i&(i<<1)))&&(!(i&(i<<2)))){
zh[++k]=i;
for(re j=i;j;j-=lowbit(j)){
++sum[k];
}
if(!(i&mp[1]))f[1][0][k]=sum[k];
}
}
for(re i=1;i<=k;++i){
for(re j=1;j<=k;++j){
if((!(zh[i]&&zh[j]))&&(!(zh[j]&mp[2])))f[2][i][j]=max(f[2][i][j],f[1][0][i]+sum[j]);
}
}
for(re i=3;i<=n;++i){
for(re j=1;j<=k;++j){//i
if(!(mp[i]&zh[j]))
for(re l=1;l<=k;++l){//father
if(!(zh[j]&zh[l]))
for(re o=1;o<=k;++o){//grand
if((!(zh[o]&zh[l]))&&(!(zh[o]&zh[j])))f[i][l][j]=max(f[i][l][j],f[i-1][o][l]+sum[j]);
}
}
}
}
int ans=0;
for(re i=1;i<=k;++i){
for(re j=1;j<=k;++j){
ans=max(f[n][i][j],ans);
}
}
cout<<ans<<endl;
}